C++ using Two Stack


  • 3
    M

    The difference between max stack and min stack is the popMax() function. When we pop element, we just have to check whether the tops of maxStk and stk are the same or not. It costs O(1) time in this operation.

    However, in the case of popMax(), the top of maxStk may not be the same as the top of stk. Therefore, the idea here is to use tmp stack to store the element of stk until we find the max element, remove it. Then, we put the elements in tmp back to stk and maxStk. It costs O(n) in worst case.

    class MaxStack {
    public:
        /** initialize your data structure here. */
        MaxStack() {
            
        }
        
        void push(int x) {  
            addMax(x);
            stk.push(x);
        }
        
        int pop() {
            int val = stk.top();
            if (stk.top() == maxStk.top()) {
                maxStk.pop();
            }
            stk.pop();
            return val;
        }
        
        int top() {
            return stk.top();
        }
        
        int peekMax() {
            return maxStk.top();
        }
        
        int popMax() {
            int val = maxStk.top();
            stack<int> tmp;
            
            while (maxStk.top() != stk.top()) {
                tmp.push(stk.top());
                stk.pop();
            } // maxStk.top() == stk.top()
            
            maxStk.pop();
            stk.pop();
            
            while (!tmp.empty()) {
                stk.push(tmp.top());
                addMax(tmp.top());
                tmp.pop();
            }
            
            return val;
        }
        
    private:
        void addMax(int x) {
            if (maxStk.empty() || x >= maxStk.top()) {
                maxStk.push(x);
            }
        }
        
        stack<int> maxStk;
        stack<int> stk;
    };
    

  • 0
    B
    This post is deleted!

  • 0
    H

    Can I ask why we need addMax() in popMax()? Supposedly, every value inside tmp stack would be smaller than maxStk.top(), so addMax will not do anything here?

    @Meng-Ju said in C++ using Two Stack:

    addMax(tmp.top());


  • 0
    M

    @helloterran said in C++ using Two Stack:

    upposedly, every value inside tmp stack would be smaller than maxStk.top(), so addMax will not do anything here?

    In this example,

    ["MaxStack","push","push","popMax","peekMax"]
    [[],[5],[1],[],[]]

    After two "push" operations,

    stk : 5, 1
    maxStk: 5

    Then, you popMax(), it will becomes the following if you don't addMax() to stk:

    stk : 1
    maxStk:

    Then, either peekMax() or popMax() will get you in trouble because there still element in stk but nothing in maxStk.


  • 0
    H

    @Meng-Ju I see, it might contain the new max value. Thanks for your explanation!


Log in to reply
 

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