155. Minimum stack

155. Smallest stack

Design a support push ,pop ,top operation , And can retrieve the stack of the smallest elements in a constant time .

Realization MinStack class :

• MinStack() Initialize stack object .
• void push(int val) Put the element val Push to stack .
• void pop() Delete the element at the top of the stack .
• int top() Get the element at the top of the stack .
• int getMin() Get the smallest element in the stack .

Input ：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output ：
[null,null,null,null,-3,null,0,-2]

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

The question ： The meaning of this question is to get the smallest number in the stack , Whether you enter or exit the stack, you finally get the smallest number in the stack .

Ideas ： Prepare two stacks , A stack is a normal stack , A stack is a stack that holds the smallest number in the stack , We also call him the minimum stack , When the two stacks are empty at first , We will put elements into these two stacks at the same time , If it's not empty , Put the element into the first ordinary stack , Then compare this element with the smallest stack top element , If it is larger than the minimum stack, the top element of the stack will not be put into the minimum stack , If it is less than the minimum stack, the top element of the stack will be put into the minimum stack .

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {// Initialize two stacks 
         stack = new Stack<>();// Ordinary stack 
         minStack = new Stack<>();// Smallest stack 
    }
    
    public void push(int val) {
        if(stack.empty()&&minStack.empty()){
            // Both stacks are empty , meanwhile push Elements 
            stack.push(val);
            minStack.push(val);
        }else {
            stack.push(val);
            if(val<=minStack.peek()){// If it is smaller than the minimum stack top element, enter 
                minStack.push(val);
            }
        }
    }
    
    public void pop() {// Out of the stack , If the output is the same as the minimum stack top element , Then at the same time, the smallest stack top element , Keep the minimum stack. The top of the stack is still the smallest element in the stack 
         int x = stack.pop();
         if(x==minStack.peek()){
             minStack.pop();
         }
    }
    
    public int top() {// Pop up the common stack top element 
         return stack.peek();
    }
    
    public int getMin() {// The minimum stack top element is the minimum 
        return minStack.peek();
    }
}