Leetcode: Min Stack

 Min Stack

My Submissions

Total Accepted: 57566 Total Submissions: 271279 Difficulty: Easy

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.

Subscribe to see which companies asked this question

Hide Tags

 Stack Design

Show Similar Problems

--------------------------------------------------------------------------
Keep two stacks inside: one store all and the other store the minimal.
Note: only the current x is smaller or equal to the mimStack.top() is saved.



///////////////////////////////////////////////////////////
class MinStack {

public:
    void push(int x) {
        curSta.push(x);
        if(minSta.empty() || x<=minSta.top() )
           minSta.push(x);
    }

    void pop() {
       
        if(minSta.top() == curSta.top() )
            minSta.pop();
        curSta.pop(); //Note: this line should be put in last, otherwise, the above codes can not be compared!!!!       
    }

    int top() {
        return curSta.top();
    }

    int getMin() {
        return minSta.top();
    }
   
private:
    stack<int> minSta;
    stack<int> curSta;  
};