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.

Thoughts:

use a auxiliary map to record the index entry, and map can sort the order internally

Code Write O(logn), read O(1):

class MaxStack {
public:
    /** initialize your data structure here. */
    list<int> l;
    map<int, vector<list<int>::iterator>> mp;

    MaxStack() {
    }

    void push(int x) {
        l.insert(l.begin(),x);
        mp[x].push_back(l.begin());
    }

    int pop() {
        // delete iterator in the map
        int key = *l.begin();
        mp[key].pop_back();
        if(mp[key].empty()) mp.erase(key);
        l.erase(l.begin());
        return key;
    }

    int top() {
        return *l.begin();
    }

    int peekMax() {
        return mp.rbegin()->first;
    }

    int popMax() {
        int key = mp.rbegin()->first;
        // get the iterator
        auto it = mp[key].back();
        mp[key].pop_back();
        if(mp[key].empty()) mp.erase(key);
        l.erase(it);
        return key;
    }
};

solution from imrusty's post