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

b'
\n\n

#### Approach #1: Two Stacks [Accepted]

\n

Intuition and Algorithm

\n

A regular stack already supports the first 3 operations, so we focus on the last two.

\n

For `peekMax`, we remember the largest value we\'ve seen on the side. For example if we add `[2, 1, 5, 3, 9]`, we\'ll remember `[2, 2, 5, 5, 9]`. This works seamlessly with `pop` operations, and also it\'s easy to compute: it\'s just the maximum of the element we are adding and the previous maximum.

\n

For `popMax`, we know what the current maximum (`peekMax`) is. We can pop until we find that maximum, then push the popped elements back on the stack.

\n

Our implementation in Python will showcase extending the `list` class.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: for the `popMax` operation, and for the other operations, where is the number of operations performed.

\n
• \n
• \n

Space Complexity: , the maximum size of the stack.

\n
• \n
\n
\n

#### Approach #2: Double Linked List + TreeMap [Accepted]

\n

Intuition

\n

Using structures like Array or Stack will never let us `popMax` quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making `popMax` faster than time complexity.

\n

Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in time.

\n

We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in time.

\n

Algorithm

\n

Let\'s store the stack as a double linked list `dll`, and store a `map` from `value` to a `List` of `Node`.

\n
\n
• \n

When we `MaxStack.push(x)`, we add a node to our `dll`, and add or update our entry `map.get(x).add(node)`.

\n
• \n
• \n

When we `MaxStack.pop()`, we find the value `val = dll.pop()`, and remove the node from our `map`, deleting the entry if it was the last one.

\n
• \n
• \n

When we `MaxStack.popMax()`, we use the `map` to find the relevant node to `unlink`, and return it\'s value.

\n
• \n
\n

The above operations are more clear given that we have a working `DoubleLinkedList` class. The implementation provided uses `head` and `tail` sentinels to simplify the relevant `DoubleLinkedList` operations.

\n

A Python implementation was not included for this approach because there is no analog to TreeMap available.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: for all operations except `peek` which is , where is the number of operations performed. Most operations involving `TreeMap` are .

\n
• \n
• \n

Space Complexity: , the size of the data structures used.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'