Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

思路 1: two stacks

通過在class中申明2個stack來分別記錄master stack和min stack

• Master stack： 正常記錄stack進行push, pop, getMin()等操作后stack的情況
• Min stack：只有當(dāng)stack為空勒虾，或者當(dāng)前要插入的值 <= min stack.peek()小的時候柱徙，才插入值，這樣就可以保證min stack棧頂?shù)脑赜肋h都是最小的。

原因： 
Master stack:  4  1  2  1
Min stack: 4 1 
(如果只插入比棧頂小的元素嗤朴，那么當(dāng)彈出1 的時候蔑滓，min stack的1將被彈出渊抄，但是此時的最小值其實還是1，但是min stack就已經(jīng)丟失了這個最小值)

Note： 為保證min stack棧頂?shù)脑赜肋h都是最小的晤锥， pop操作時必須要進行一次判斷，判斷pop的這個元素是否= = min stack棧頂?shù)脑? 如果相等廊宪，此時需要同時彈出min stack棧頂?shù)脑亍?/p>

class MinStack {
    Stack<Integer> mainStack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();
    
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        mainStack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
            System.out.println("push min");
        }
    }
    
    public void pop() {
        int cur = 0;
        if (!mainStack.isEmpty()) {
            cur = mainStack.pop();
        }
        
        if (!minStack.isEmpty() && cur == minStack.peek()) {
            minStack.pop();
        } 
        
    }
    
    public int top() {
        if (!mainStack.isEmpty()) {
            return mainStack.peek();
        }
        return Integer.MIN_VALUE;
    }
    
    public int getMin() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        } 
        return Integer.MIN_VALUE;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Solution2: One Stack for main stack, one priorityQueue for minHeap which keep an ascending number list

class MinStack {
    Stack<Integer> stack;
    PriorityQueue<Integer> minHeap;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer> ();
        minHeap = new PriorityQueue<Integer> ();
    }
    
    public void push(int x) {
        stack.push (x);
        minHeap.offer (x);
    }
    
    public void pop() {
        int popedNumber = stack.pop ();
        if (minHeap.peek () == popedNumber) {
            minHeap.poll ();
        }
    }
    
    public int top() {
        return stack.peek ();
    }
    
    public int getMin() {
        return minHeap.peek ();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */