## Question

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the `MaxStack`

class:

`MaxStack()`

Initializes the stack object.`void push(int x)`

Pushes element`x`

onto the stack.`int pop()`

Removes the element on top of the stack and returns it.`int top()`

Gets the element on the top of the stack without removing it.`int peekMax()`

Retrieves the maximum element in the stack without removing it.`int popMax()`

Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the**top-most**one.

You must come up with a solution that supports `O(1)`

for each `top`

call and `O(logn)`

for each other call.

**Example 1:**

```
Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]
Explanation
MaxStack stk = new MaxStack();
stk.push(5); // [5] the top of the stack and the maximum number is 5.
stk.push(1); // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5); // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top(); // return 5, [5, 1, 5] the stack did not change.
stk.popMax(); // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top(); // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop(); // return 1, [5] the top of the stack and the max element is now 5.
stk.top(); // return 5, [5] the stack did not change.
```

**Constraints:**

`-107 <= x <= 107`

- At most
`105`

calls will be made to`push`

,`pop`

,`top`

,`peekMax`

, and`popMax`

. - There will be
**at least one element**in the stack when`pop`

,`top`

,`peekMax`

, or`popMax`

is called.

## Algorithm1

In this problem, we are required to implement a data structure based on a classic stack, supporting `pop`

and `top`

methods in a stack. It is not hard to implement such a LIFO (Last-In-First-Out) stack to return and remove the **last added** element. However, we need to implement `popMax`

and `peekMax`

to return and remove the **max** element in the entire stack additionally, which makes the requirement become much more tricky.

We may easily come up with the idea to track the last pushed and the max element so far **separately**, so we can find the last or the max element quickly for a single operation of `top`

or `peekMax`

. But the primary challenge is to figure out an efficient way to remove a specified element in both records of the push order track and the value track. Otherwise, we will fail to find out the exact last or max value in the next query method call.

#### Intuition

To peek or pop the max element quickly, we may think of a heap (or priority queue). Meanwhile, a classic stack is sufficient to peek or pop the last added element quickly. What if we keep the two data structures at the same time?

Yes, we can pop the max or the last element quickly. However, when we pop the top element of our heap or the stack, we don't know how to locate the removed element in the other one unless we enumerate all items in it from top to bottom.

Thus, we are not urgent to delete the popped element. Instead, we just memorize the ID of this element. Next time, when we are going to peek or pop the top of our heap or stack, we first check whether the top is already removed from the other data structure by checking its ID.

#### Algorithm

To memorize all IDs of deleted elements, we use a hash set `removed`

to store them. Apart from the stack(`stack`

) and max heap(`heap`

) we mentioned above, we still need a counter `cnt`

like Approach 1 to tag each element with a unique ID.

Whenever `push(x)`

is called, we add it along with the current counter value into both `heap`

and `stack`

, then increase our `cnt`

by 1.

Whenever we are requested to operate on `stack`

or `heap`

(i.e., `top`

, `pop`

, `peekMax`

and `popMax`

), we first check the ID of its top element, if is turns out to be an ID in `removed`

, that is, it was removed previously, we need to **remove the current top element until its ID is not in removed** to make sure the top still exists. After that,

- For
`top`

, return the value of the top element in`stack`

. - For
`peekMax`

, return the value of the top element in`heap`

. - For
`pop`

, remove the top element of`stack`

, put its ID into`removed`

, and return its value. - For
`popMax`

, remove the top element of`heap`

, put its ID into`removed`

, and return its value.

We can observe that we only check the existence of the top element and remove the element only when it is at the top because the deletion operation for the top of a stack or heap is much faster.

## Code1

class MaxStack { private Stack<int[]> stack; private Queue<int[]> heap; private Set<Integer> removed; private int cnt; public MaxStack() { stack = new Stack<>(); heap = new PriorityQueue<>((a, b) -> a[0] - b[0] == 0 ? b[1] - a[1] : b[0] - a[0]); removed = new HashSet<>(); } public void push(int x) { stack.push(new int[] {x, cnt}); heap.add(new int[] {x, cnt}); cnt++; } public int pop() { while (removed.contains(stack.peek()[1])) { stack.pop(); } int[] top = stack.pop(); removed.add(top[1]); return top[0]; } public int top() { while (removed.contains(stack.peek()[1])) { stack.pop(); } return stack.peek()[0]; } public int peekMax() { while (removed.contains(heap.peek()[1])) { heap.poll(); } return heap.peek()[0]; } public int popMax() { while (removed.contains(heap.peek()[1])) { heap.poll(); } int[] top = heap.poll(); removed.add(top[1]); return top[0]; } } /** * 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(); */

## Algorithm2

#### Intuition

The main challenge in the design is how to track the max and the last element respectively. Naturally, we consider keeping two copies of all elements stack, one is in the pushing order, and the other is sorted by the elements' values. A balanced tree is perfect for keeping all elements sorted in some specified order **dynamically**. We can use two balanced trees to track the order of pushing and values respectively. Once we need to remove the largest element in either balanced tree, we can also easily locate and remove it in the other balanced tree.

#### Algorithm

As we discussed in Intuition, we need to maintain two balanced trees respectively: the former is in pushing order (`stack`

), and the latter is sorted by values (`values`

). Besides, we also need to tag each element with a unique `id`

. To ensure all elements are of different `id`

s, we keep a counter `cnt`

, which increases by one once an element is pushed into our stack.

For `push`

operation, we need to push the element with the current `cnt`

into both two balanced trees, `stack`

and `values`

, which insert the element by `id`

and `val`

respectively. And then, don't forget to increase `cnt`

.

For `top`

and `peekMax`

, since `stack`

and `values`

are sorted by the pushing order and element values, we only need to return the last element value of `stack`

for `top`

query, and the last element value of `values`

for `peekMax`

.

For `pop`

and `popMax`

, besides what we do before, we still find and remove the returned element in both two balanced trees. For `pop`

, we first remove the last element in `stack`

, and then remove the element in `values`

; for `popMax`

, we first remove the last element in `values`

, and then remove the element in `stack`

.

For example, let's take a look at the input in example 1:

```
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
```

After the first three `push`

calls, our `stack`

and `values`

are sorted as:

```
stack = [(id:0, val:5), (id:1, val:1), (id:2, val:5)]
values = [(id:1, val:1), (id:0, val:5), (id:2, val:5)]
```

Then, `top`

returns the last element in `stack`

, whose value is 5;

`popMax`

is about to remove the last element in `values`

, `(id:2, val:5)`

, in both `stack`

and `values`

. So after `popMax`

returns `5`

, the two balanced trees are:

```
stack = [(id:0, val:5), (id:1, val:1)]
values = [(id:1, val:1), (id:0, val:5)]
```

Then, `top`

returns the last element in `stack`

, whose value is `1`

; Similar, the following `peekMax`

returns the last element in `values`

, whose value is `5`

.

After `pop`

is called, we remove `(id:1, val:1)`

and return the value `5`

, so:

```
stack = [(id:0, val:5)]
values = [(id:0, val:5)]
```

Finally, the last call of `top`

gives the only element `(id:0, val:5)`

, whose value is `5`

.

## Code2

class MaxStack { private TreeSet<int[]> stack; private TreeSet<int[]> values; private int cnt; public MaxStack() { Comparator<int[]> comp = (a, b) -> { return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]; }; stack = new TreeSet<>(comp); values = new TreeSet<>(comp); cnt = 0; } public void push(int x) { stack.add(new int[] { cnt, x }); values.add(new int[] { x, cnt }); cnt++; } public int pop() { int[] pair = stack.pollLast(); values.remove(new int[] { pair[1], pair[0] }); return pair[1]; } public int top() { return stack.last()[1]; } public int peekMax() { return values.last()[0]; } public int popMax() { int[] pair = values.pollLast(); stack.remove(new int[] { pair[1], pair[0] }); return pair[0]; } }