C++ solution with 2 stacks, just like minStack


  • 1
    M

    O(n) for popMax and O(1) for the rest

        int mx=INT_MIN;
        stack<int> stk;
        MaxStack() {
            
        }
        
        void push(int x) {
            if(stk.empty()) {
                mx=x;
                stk.push(0);
            }
            else {
                stk.push(x-mx);
                mx=max(mx, x);
            }
        }
        
        int pop() {
            if(stk.top()>=0) mx-=stk.top();
            int res=stk.top();
            stk.pop();
            return res+mx;
        }
        
        int top() {
            if(stk.top()>=0) return mx;
            return stk.top()+mx;
        }
        
        int peekMax() {
            return mx;
        }
        
        int popMax() {
            int tm=mx;
            stack<int> temp; 
            while(stk.top()<0) {
                temp.push(stk.top());
                stk.pop();
            }
            mx-=stk.top();
            stk.pop(); 
            while(!temp.empty()) {
                push(tm+temp.top());
                temp.pop();
            }
            return tm;
        }

Log in to reply
 

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