Min Stack

實作一個「最小Stack」，支援 push(), pop(), top(), getMin() 的操作

getMin() 總是回傳 stack 裡的最小值，而且這個操作要在 O(1) 時間內完成

直覺的想法是在元素 push() 的過程中，用一個 int min 紀錄最小值，

可是當我們 pop() 時，有可能把最小值 pop 掉，那這樣就無法在 O(1) 時間內取得最小值

所以要反過來想，如果有個地方可以同時紀錄某元素 push 進去時的最小值就好了

我們可以額外開一個 minStack，專門紀錄某元素推入的時候，相對應的最小值，

那在 pop 時，也把 minStack 同時 pop 掉，那 getMin() 就會是 O(1) 的操作

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else {
            minStack.push(Math.min(x, minStack.peek()));
        }
    }

    public void pop() {
        minStack.pop();
        stack.pop();
    }

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

    public int getMin() {
        return minStack.peek();
    }
}