我們一起聊聊包含min函數的棧
作者：神奇的程序員
相信大多數開發者看到這個問題，第一反應可能是每次往棧中壓入一個新元素時，將棧里的所有元素排序，讓最小的元素位于棧頂，這樣就能在O(1)的時間內得到最小元素了。但這種思路不能保證最后入棧的元素能夠最先出棧，因此這個思路行不通。
前言
基于數據結構: “棧”，實現一個min函數，調用此函數即可獲取棧中的最小元素。在該棧中，調用min、push、pop的時間復雜度都是O(1)。
思路梳理
相信大多數開發者看到這個問題，第一反應可能是每次往棧中壓入一個新元素時，將棧里的所有元素排序，讓最小的元素位于棧頂，這樣就能在O(1)的時間內得到最小元素了。但這種思路不能保證最后入棧的元素能夠最先出棧，因此這個思路行不通。
緊接著，我們可能會想到用一個變量來存放最小的元素，每次壓入一個新元素入棧時，如果它比當前最小的元素還要小，則更新最小元素。這樣子做目的是達到了，但是又會有另一個問題：如果當前最小元素被彈出棧了，那么如何得到下一個最小的元素？
很顯然，我們僅僅添加一個變量用來存儲最小元素是不夠的，也就是說當最小元素被取出時，我們希望得到次最小元素。那么，我們能否用一個輔助棧專門來存放這些最小元素呢？當元素入棧時，我們就取出輔助棧中的棧頂元素將其與新加入元素做大小比較，把較小的一方壓入輔助棧中。
我們通過一個例子來講解下這個過程，如下所示：
const stack = [
3,
5,
7
12,
1,
9,
0
]
入棧過程如下圖所示：
出棧時，我們同時彈出兩個棧的棧頂元素，獲取最小元素時，我們將輔助棧的棧頂元素返回即可，過程如下圖所示：
實現代碼
經過前面的分析，我們已經得出了完整的思路，接下來就是編碼環節了，如下所示：
export class StackContainingMinFunction extends Stack {
private minStack: Stack;
private dataStack: Stack;
constructor() {
super();
this.minStack = new Stack();
this.dataStack = new Stack();
}
public push(item: number): void {
this.dataStack.push(item);
if (this.minStack.size() > 0) {
const minVal = this.minStack.peek();
// 比較當前入棧元素與minStack中的最小元素，將小的一方入minStack
item > minVal ? this.minStack.push(minVal) : this.minStack.push(item);
return;
}
this.minStack.push(item);
}
public pop(): void {
this.minStack.pop();
this.dataStack.pop();
}
public min(): number | null {
if (this.minStack.size() > 0) return this.minStack.peek();
return null;
}
}
注意：上述代碼繼承了Stack，我們在之前文章中已經實現了它，對此感興趣的開發者請移步：數組實現棧與對象實現棧的區別
我們將上個章節的例子代入上述實現的函數中，來看下它能否正確運行。
const stackMinFn = new StackContainingMinFunction();
stackMinFn.push(3);
stackMinFn.push(5);
stackMinFn.push(7);
stackMinFn.push(12);
stackMinFn.push(1);
stackMinFn.push(9);
stackMinFn.push(0);
stackMinFn.pop();
stackMinFn.pop();
stackMinFn.pop();
console.log("當前棧內最小值為:", stackMinFn.min());
示例代碼
本文所列舉的代碼完整版請移步：
- StackContainingMinFunction.ts
- stackContainingMinFunction-test.ts
責任編輯：武曉燕
來源：
神奇的程序員
