155. 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.

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.

 Solution:
to getMin, scan all elements need O(n). to getMin in O(1), need to store the min value in a variable or a stack. The min value is changed while pop up or push the element, so use a min stack to store the min value of any time. The min stack keep the min value of the current stack on the top always.
Push x
  if the stack is empty, push the new element x.
  if the peek of the stack is larger than new element x, push the new element.
  if the peek of the stack is smaller than new element x, push the peek of the stack(there will be duplicate element in min stack. because the smallest element may be the same)
the elements number of min stack and main stack is the same.
Pop
  pop the min stack and main stack.

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> stack1;
    Stack<Integer> min;
    public MinStack() {
        stack1 = new Stack<Integer>();
        min = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if(min.isEmpty() || x < min.peek()){
            min.push(x);
        }else{
            min.push(min.peek());
        }
    }
    
    public void pop() {
        stack1.pop();
        min.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}