Stack Supporting Removal of Its Own Maximum Element
Implement stackOpsMax
Design a stack that supports the usual
push, pop, and top, plus peekMax (return the current maximum without removing it) and popMax (remove and return the current maximum — which might not be on top of the stack at all, and could be buried anywhere below it).
peekMax reuses the same parallel-stack trick as tracking a running minimum: a second stack records the running maximum at every depth, so reading it is always O(1). popMax is the harder part, since the maximum being removed usually isn't the topmost element — everything above it has to move out of the way and then come back. The clean way to do that is a temporary buffer: pop elements (from both stacks together) into the buffer until the real maximum surfaces on top, discard it, then push the buffered elements back on in their original order, recomputing each one's max-stack entry as it's restored. Nothing above the maximum is lost or reordered — it's just temporarily set aside.
Example 1:
Input: ops = ["push","push","push","peekMax","popMax","top","peekMax"], args = [4,9,3,0,0,0,0]
Output: [9,9,3,4]
Example 2:
Input: ops = ["push","push","push","push","popMax","popMax","top"], args = [2,7,7,5,0,0,0]
Output: [7,7,5]
Example 3:
Input: ops = ["push","pop","peekMax","push","push","popMax","pop"], args = [6,0,0,1,8,0,0]
Output: [6,-1,8,1]
+ 2 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ ops.length ≤ 20 - ●
ops[i] is one of "push", "pop", "top", "peekMax", "popMax"; args[i] is the value to push (0 for every other operation, unused) - ●
"pop", "top", "peekMax", and "popMax" on an empty stack each return -1 - ●
If the maximum value appears more than once, popMax removes the topmost (most recently pushed) occurrence
ops =
["push", "push", "push", "peekMax", "popMax", "top", "peekMax"]
args =
[4, 9, 3, 0, 0, 0, 0]