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.

// Two Stacks
class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        if (s2.empty() || s2.top() <= x) s2.push(x);
        s1.push(x);
    }
    
    int pop() {
        if (!s2.empty() && s1.top() == s2.top()) s2.pop();
        int val = s1.top(); s1.pop();
        return val;
    }
    
    int top() {
        return s1.top();
    }
    
    int peekMax() {
        return s2.top();
    }
    
    int popMax() {
        int maxVal = s2.top();
        stack<int> tmp;
        while (s1.top() != s2.top()) {
            tmp.push(s1.top()); s1.pop();
        }
        s1.pop(); s2.pop();
        while (!tmp.empty()) {
            push(tmp.top()); tmp.pop();
        }
        return maxVal;
    }
private:
    stack<int> s1, s2;
};

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