155 Min Stack

Solution 1

O(1)

首先使用一個變數min來儲存stack中最小的值，這樣getMin()就符合O(1)，速度會快很多

1. 因此就要改成在push跟pop的地方動手腳，push的時候，如果加入的x小於等於min，除了讓min=x，我們還先把目前的min加到stack中
2. 以下用[2,3]這個堆疊作範例，目前min = 2， stack.push(1)，1小於2，所以將2先加入stack再把1加入，stack=[2,3,2,1]
3. 如此一來getMin()的時候會直接回傳1，對top()這個方法也沒任何的影響，但是pop()的時候就會有問題了
4. stack.pop()移除最上面的元素，stack=[2,3,2]，跟正確的stack=[2,3]明顯是不一樣的，而且min也沒更新為2
5. 這時候之前多放入的第二小的數[2]，就發揮作用了，讓min = 2，然後再把這個2移除，stack = [2,3]，min也變成了2，重此之後世界又恢復了和平

class MinStack {
    Stack<Integer> stack;
    int min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        int popVal = stack.pop();
        if(popVal == min){
            min = stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}