155. Min Stack

Problem:

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.

Analysis:
每当有极小数的时候，先把次小数push进stack,然后把极小数push进stack。当pop的数是当前min的时候，连续pop 2次，第二次的就是pop后的min.
push -2
    stack -2, max] min: -2
push 0
    stack 0, -2, max] min: -2
push -3
    stack -3, -2, 0, -2, max] min: -3
pop:
    这里先pop-3出去，发现-3刚好是最小值，所以把 -2也pop出去，-2就是去除-3后的最小值。

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

class MinStack { int min = Integer.MAX_VALUE; Stack<Integer> stack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); } public void push(int x) { if (x <= min) { stack.push(min); min = x; } stack.push(x); } public void pop() { if (stack.pop() == min) min = stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return min; } } /** * 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(); */