716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

class MaxStack {

private:

    stack<int> st, maxSt;

public:

    /** initialize your data structure here. */

    MaxStack() {

        

    }

    

    void push(int x) {

        if (maxSt.empty() || maxSt.top() < x) {

            maxSt.push(x);

        } else {

            maxSt.push(maxSt.top());

        }

        st.push(x);

    }

    

    int pop() {

        int val = st.top();

        st.pop();

        maxSt.pop();

        return val;

    }

    

    int top() {

        return st.top();

    }

    

    int peekMax() {

        if (maxSt.empty()) {

            int ans;

            return ans;

        }

        return maxSt.top();

    }

    

    int popMax() {

        int ans = maxSt.top();

        stack<int> tmp;

        while (st.top() != ans) {

            tmp.push(st.top());

            st.pop();

            maxSt.pop();

        }

        st.pop();

        maxSt.pop();

        while (!tmp.empty()) {

            st.push(tmp.top());

            int temp = maxSt.empty() ? tmp.top() : max(maxSt.top(), tmp.top());

            maxSt.push(temp);

            tmp.pop();

        }

        return ans;

    }

};

==============

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {}
    
    void push(int x) {
        v.insert(v.begin(), x);
        m[x].push_back(v.begin());
    }
    
    int pop() {
        int x = *v.begin();
        m[x].pop_back();
        if (m[x].empty()) m.erase(x);
        v.erase(v.begin());
        return x;
    }
    
    int top() {
        return *v.begin();
    }
    
    int peekMax() {
        return m.rbegin()->first;
    }
    
    int popMax() {
        int x = m.rbegin()->first;
        auto it = m[x].back();
        m[x].pop_back();
        if (m[x].empty()) m.erase(x);
        v.erase(it);
        return x;
    }

private:
    list<int> v;
    map<int, vector<list<int>::iterator>> m;
};

=========

class MaxStack {
public:
    list<int> v;
    map<int, vector<list<int>::iterator>> mp;
    
    MaxStack() { 
    }
    
    void push(int x) {
        v.insert(v.begin(),x);
        mp[x].push_back(v.begin());
    }
    
    int pop() {
        int x = *v.begin();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        v.erase(v.begin());
        return x;
    }
    
    int top() {
        return *v.begin();
    }
    
    int peekMax() {
        return mp.rbegin()->first;
    }
    
    int popMax() {
        int x = mp.rbegin()->first;
        auto it = mp[x].back();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        v.erase(it);
        return x;
    }
};