Leetcode-155: minimum stack

subject

Topic linking

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 .

Example 1:

 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.
 

Problem solving

and The finger of the sword Offer 30： contain min Function of the stack equally

Method 1 ： Auxiliary stack

class MinStack {
    
public:
    stack<int> st1;
    stack<int> st2;
    MinStack() {
    

    }
    
    void push(int val) {
    
        if(st1.empty()) st2.push(val);
        else st2.push(min(val,st2.top()));
        
        st1.push(val);
    }
    
    void pop() {
    
        st1.pop();
        st2.pop();
    }
    
    int top() {
    
        return st1.top();

    }
    
    int getMin() {
    
        return st2.top();

    }
};