716. Max Stack

Practice Max Stack for free on NudgeCode: Hard, Stack pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design a stack that can also find and remove its largest element:

• push(x) puts x on top.
• pop() removes the top element and returns it.
• top() returns the top element without removing it.
• peekMax() returns the largest element without removing it.
• popMax() removes the largest element and returns it. If the largest value appears more than once, remove the copy closest to the top.

Aim for O(log n) per call (top may be O(1)). Each test is a list of operations and their arguments; the expected output lists what each call returns (null for calls that return nothing).

Example

["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"]
[[],[5],[1],[5],[],[],[],[],[],[]]
->  [null,null,null,null,5,5,1,5,1,5]

After pushing 5, 1, 5, popMax removes the upper 5, so the top becomes 1 while the maximum is still the lower 5.

Constraints

• -10^7 <= x <= 10^7
• at most 10^5 calls in total
• pop, top, peekMax and popMax are only called on a non-empty stack