## 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

``````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