Implement with stack and pair. All operations have O(1) time complexity.


  • 5
    A

    each element in stack is a pair of two int. The first is the int that we want to push into the stack. And the other one is the minimum value of the stack at this moment.

    class MinStack {
    private:
    stack<pair<int, int>> sta;
    public:
    void push(int x) {
        if(sta.empty()) 
            sta.push(make_pair(x, x));
        else {
            auto top = sta.top();
            sta.push(make_pair(x, x < top.second ? x : top.second));
        }
    }
    
    void pop() {
        if(!sta.empty())
            sta.pop();
    }
    
    int top() {
        if(!sta.empty())
            return sta.top().first;
        else
            return -1;
    }
    
    int getMin() {
        if(!sta.empty())
            return sta.top().second;
        else 
            return -1;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.