Min Stack

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.

我在面zenefits的时候被问过这题，当时没想出来，后来得到提示需要使用两个Stack, 第一个Stack用来按顺序存放入的元素，第二个Stack用来记录比当前Stack的top element小的元素。

原始栈 - |2,1,3,4,1,2|

最小栈 - |2,1,1|

pop(2) - |2,1,1|

pop(1) - |2,1|

pop(4) - |2,1|

pop(3) - |2,1|

pop(1) - |2|

pop(2) - ||

class MinStack {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()||minStack.peek()>=x) {
            minStack.push(x);
        }
    }

    public void pop() {
        int value = stack.pop();
        if (minStack.peek()==value) {
            minStack.pop();
        }

    }

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

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