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：只有当stack为空，或者当前要插入的值 <= min stack.peek()小的时候，才插入值，这样就可以保证min stack栈顶的元素永远都是最小的。

原因： 
Master stack:  4  1  2  1
Min stack: 4 1 
(如果只插入比栈顶小的元素，那么当弹出1 的时候，min stack的1将被弹出，但是此时的最小值其实还是1，但是min stack就已经丢失了这个最小值)

Note： 为保证min stack栈顶的元素永远都是最小的， pop操作时必须要进行一次判断，判断pop的这个元素是否= = min stack栈顶的元素. 如果相等，此时需要同时弹出min stack栈顶的元素。

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();
 */