the stack is implemented in linked list so we can remove element in ** O(1)** time when call

*popMax()*the node pointers are stored in ** std::map**, since all keys in

**are sorted so we can always find max element in**

*std::map***time through the**

*O(1)***iterator**

*rbegin*** push()** would be

**since we need to do an insert in**

*O(log n)*

*std::map*** pop()** would be

**since we need to do find and deletion in**

*O(log n)*

*std::map*```
class MaxStack {
public:
struct ListNode
{
int val;
ListNode* prev;
ListNode* next;
ListNode(int v = 0):val(v), prev(nullptr), next(nullptr){};
};
ListNode * head;
ListNode * tail;
map<int, vector<ListNode*>> address;
/** initialize your data structure here. */
MaxStack() {
head = new ListNode();
tail = new ListNode();
head -> next = tail;
tail -> prev = head;
}
void push(int x) {
ListNode * node = new ListNode(x);
node -> next = head -> next;
head -> next -> prev = node;
head -> next = node;
node -> prev = head;
address[x].push_back(node);
}
int pop() {
ListNode * node = head -> next;
head -> next = node -> next;
node -> next -> prev = head;
address[node->val].pop_back();
if(address[node->val].empty())
address.erase(node->val);
return node->val;
}
int top() {
return head -> next -> val;
}
int peekMax() {
return address.rbegin()->second.back() -> val;
}
int popMax() {
//get node address
ListNode * node = address.rbegin()->second.back();
//remove node from stack
node -> prev -> next = node -> next;
node -> next -> prev = node -> prev;
//remove node from address, if vector is empty, remove key
address[node->val].pop_back();
if(address[node->val].empty())
address.erase(node->val);
return node -> val;
}
};
/**
* Your MaxStack object will be instantiated and called as such:
* MaxStack obj = new MaxStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.peekMax();
* int param_5 = obj.popMax();
*/
```