我們今天的面試題是這樣的...

題目

定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間復雜度都是 O(1)。

示例： 

MinStack minStack = new MinStack();  
minStack.push(-2);  
minStack.push(0);  
minStack.push(-3);  
minStack.min(); --> 返回 -3.  
minStack.pop();  
minStack.top(); --> 返回 0.  
minStack.min(); --> 返回 -2.  
LeetCode 地址：leetcode-cn.com/problems/ba… 

思考

首先來說這道題目本身很好理解，它的實現難點在于以下兩個方面：

• 當我們進行 pop(移除棧頂元素)操作時如果刪除的是當前最小值，那么我們如何尋找下一個最小值?
• 要保證調用 min、push 及 pop 的時間復雜度都是 O(1)。

也就是說，在我們執行了 pop 時如果移除的棧中最小的值，那么如何尋找棧中的下一個最小元素?并且要保證操作的時間復雜度為 O(1)。這個時間復雜度制約了我們在移除了最小值之后不能通過遍歷查找下一個最小值，所以這就成為了這道題的難點。

比如當我們移除以下棧頂元素值： 

因為最小值就是 1，因此在移除之后最小值也被移除了，如下圖所示：

那么接下來，讓我們一起思考 3 分鐘，想一想應該如何處理這個問題~

解題思路

其實我們可以在每次入棧時，判斷當前元素是否小于最小值，如果小于則將原最小值和最新的最小值相繼入棧，這樣在調用 pop 時即使移除的是最小值，我們也能通過獲取下一個元素得到一個新的最小值，執行流程如下所示。

操作步驟1

入棧第一個元素，因為是第一個元素，因此最小值就是此元素的值。 

操作步驟2

入棧第二個元素，如下圖所示： 

因為入棧的元素 3 比 8 小，所以先將棧中的原最小值 8 存入棧中，再將 3 入棧。

操作步驟3

入棧第三個元素，如下圖所示： 

因為入棧元素 5 大于 3，因此棧中的最小值不變，直接將元素 5 入棧。

操作步驟4

繼續入棧，如下圖所示： 

入棧元素 1 小于 3，因此先將原最小值 3 入棧，再將 1 入棧，棧中的最小值更改為 1。

操作步驟5

執行出棧操作，如下圖所示： [圖片上傳中...(image-f68dcf-1602769401330-6)]

元素 1 出棧，判斷當前元素就是棧的最小值，因此將棧頂元素 3 設置為最小值，并移除元素 3，如下圖所示： 

操作步驟6

繼續出棧，如下圖所示： 

因為元素 5 不是當前最小值，因此直接出棧。

操作步驟7

繼續出棧，如下圖所示： 

因為出棧元素 3 為最小值，因此繼續將最小值設置為棧頂元素 8，并將棧頂元素出棧，如下圖所示： 

這樣就剩下最后一個元素了，最后一個元素出棧之后就成空棧了，整個流程就執行完了。

實現代碼1

接下來我們將上面的思路用代碼實現一下，我們用數組實現的棧來實現相關的功能，代碼如下： 

class MinStack { 
    private int[] data; // 棧數據 
    private int maxSize; // 最大長度 
    private int top; // 棧頂指針（下標） 
    private int min; // 最小值 
 
    // 構造函數 
    public MinStack() { 
        // 設置默認值 
        maxSize = 10000; 
        data = new int[maxSize]; 
        top = -1; 
        min = Integer.MAX_VALUE; 
    } 
 
    // 入棧（添加元素） 
    public void push(int x) { 
        if (min >= x) { 
            // 遇到了更小的值，記錄原最小值（入棧） 
            data[++top] = min; 
            min = x; 
        } 
        // 當前值入棧 
        data[++top] = x; 
    } 
 
    // 出棧（移除棧頂元素） 
    public void pop() { 
        if (min == data[top]) { 
            min = data[--top]; // 拿到原最小值，并（將原最小值）出棧 
        } 
        --top; // 出棧 
    } 
 
    // 查找棧頂元素 
    public int top() { 
        return data[top]; 
    } 
 
    // 查詢最小值 
    public int min() { 
        return min; 
    } 
} 

上述代碼在 LeetCode 的執行結果如下： 

可以看出性能還是很高的，超越了 99.92% 的用戶，內存消耗也不大。它的核心代碼在 push 方法內，先將原最小值和最新最小值相繼入棧，在 pop 出棧時判斷出棧元素是否為最小值，如果是最小值則將當前最小值指向棧頂元素并將棧頂元素出棧，這樣就得到了下一個新的最小值了。

實現代碼2

如果我們不想使用數組的自定義棧來實現，還可以使用 Java 中自帶的棧 Stack 來實現此功能，代碼如下： 

class MinStack { 
    private Stack<Integer> stack = new Stack<>(); 
    private int min = Integer.MAX_VALUE; 
 
    public MinStack() { } 
 
    // 入棧（添加元素） 
    public void push(int x) { 
        if (x <= min) { 
            // 遇到了更小的值，記錄原最小值（入棧） 
            stack.push(min); 
            min = x; 
        } 
        stack.push(x); 
    } 
 
    // 出棧（移除棧頂元素） 
    public void pop() { 
        if (stack.pop() == min) { 
            min = stack.pop(); // 取出原最小值 
        } 
    } 
 
    // 查找棧頂元素 
    public int top() { 
        return stack.peek(); 
    } 
 
    // 查詢最小值 
    public int min() { 
        return min; 
    } 
} 

上述代碼在 LeetCode 的執行結果如下： 

從結果可以看出，使用 Java 中自帶的棧的性能不如自定義數組的棧，但代碼還是通過了測試。這種實現方式的優點就是代碼比較簡單，可以利用了 Java 自身的 API 來完成了最小值的查找。

這種實現代碼的方式(使用 Java API)，在刷題或者實際面試中如果沒有特殊說明是可以直接用的。

總結

本文我們通過兩種方式：自定義數組棧和 Java API 中的 Stack 來實現了棧中最小值的功能，保證了在調用棧的 min、push 及 pop 方法時的時間復雜度都是 O(1)。兩種實現方式的代碼雖然略不相同，但實現思路都是一樣的，都是在元素入棧時判斷當前元素是否小于最小元素，如果小于最小元素則先將原最小值入棧，再將當前最小元素入棧，這樣當調用 pop 方法時，即使移除的是最小值，只需要將下一個元素取出即為新的最小值了，這樣就可以實現調用 min、push 及 pop 方法時的時間復雜度都是 O(1) 了。