題目：
寫一個能知道目前stack中最小值的stack
操作時間必須是constant time

舉例：
這題舉例會超級長，請見LeetCode上面的舉例

點我前往LeetCode題目
(這題和CTCT 3.2一樣喔)

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

不知道constant time、O(1)的話，請這樣理解：

你不可以在call程式要最小值時，再去loop整個stack找最小值

聽起來必須隨時記住stack中的最小值對吧？

對，就是必須這樣做才行。如果不能夠loop，就必須額外開空間來存，而且存數字進去的當下，就必須要記錄當下的最小值

在開始之前，我們需要認識一個方法，就是peek()。他的作用是告訴我們stack最上面的值，而且不把它刪掉（pop()是拿值+刪掉）

接下來，我們需要兩條stack，一條正常的記進來的值，一條記當下最小的值。當正常的stack塞東西進去時，我們也同步塞當時最小的值進去，所以兩條stack相同位置的數字就會互相對應到。

我們從程式碼解釋吧！

class MinStack {
    Stack<Integer> s;
    Stack<Integer> mins;
    
    /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<Integer>();
        mins = new Stack<Integer>();
    }
    
    public void push(int x) {
        if(s.isEmpty() || x <= mins.peek()){
            mins.push(x);
        }else{
            mins.push(mins.peek());
        }
        s.push(x);
    }
    
    public void pop() {
        s.pop();
        mins.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return mins.peek();
    }
}

我們逐一解釋下去

Stack<Integer> s;
Stack<Integer> mins;
    
/** initialize your data structure here. */
public MinStack() {
    s = new Stack<Integer>();
    mins = new Stack<Integer>();
}

總之先幫我們建兩條要用的stack出來，s用來正常記值，mins用來記當下最小的值

public void push(int x) {
    if(s.isEmpty() || x <= mins.peek()){
        mins.push(x);
    }else{
        mins.push(mins.peek());
    }
    s.push(x);
}

這個mins的push()是怎麼運作的呢？就是每次有新數字進s，先和mins最外面的數字比較，因為最外面的數字是數字進來前的最小值，我們拿新進來的數字和之前的最小值相比，更小就塞進mins，沒有的話就再把之前的最小值塞進去

上面或許有點饒舌，所以下面提供一張個人製作的GIF，看這個應該更清楚
（stack代表正常存值的那條，minStack就是專門記最小值的那條）

public void pop() {
    s.pop();
    mins.pop();
}

注意，如果原本的stack要pop，mins也要一起pop掉對應的最小值喔

public int top() {
    return s.peek();
}
    
public int getMin() {
    return mins.peek();
}

top()和getMin()就理所當然的用peek()偷看一下s/mins最外面的東西

解決！