This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Design a max stack that supports push, pop, top, peekMax and popMax.

- push(x) -- Push element x onto stack.
- pop() -- Remove the element on top of the stack and return it.
- top() -- Get the element on the top.
- peekMax() -- Retrieve the maximum element in the stack.
- 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:**

- -1e7 <= x <= 1e7
- Number of operations won't exceed 10000.
- The last four operations won't be called when stack is empty.

b'

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

\n

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

\n

\n

'
**Intuition and Algorithm**

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

\nFor `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.

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.

Our implementation in Python will showcase extending the `list`

class.

**Complexity Analysis**

- \n
- \n
Time Complexity: for the

\n`popMax`

operation, and for the other operations, where is the number of operations performed. \n - \n
Space Complexity: , the maximum size of the stack.

\n \n

\n

**Intuition**

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.

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.

\nWe 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**

Let\'s store the stack as a double linked list `dll`

, and store a `map`

from `value`

to a `List`

of `Node`

.

- \n
- \n
When we

\n`MaxStack.push(x)`

, we add a node to our`dll`

, and add or update our entry`map.get(x).add(node)`

. \n - \n
When we

\n`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
When we

\n`MaxStack.popMax()`

, we use the`map`

to find the relevant node to`unlink`

, and return it\'s value. \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.

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

**Complexity Analysis**

- \n
- \n
Time Complexity: for all operations except

\n`peek`

which is , where is the number of operations performed. Most operations involving`TreeMap`

are . \n - \n
Space Complexity: , the size of the data structures used.

\n \n

\n

Analysis written by: @awice.

\n