716. Max Stack
Design a stack that supports the following operations in O(1) time:
push(x): Push element x onto stackpop(): Remove and return the top elementtop(): Return the top element without removing itpeekMax(): Return the maximum element in the stackpopMax(): Remove and return the maximum element in the stack
Examples
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]
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]
Hints
Use two stacks: one for regular operations, one to track maximums.
For popMax, you may need to temporarily transfer elements to find the maximum.
Alternatively, use a doubly-linked list with a separate max-tracker structure.
Related Problems
716. Max Stack
Design a stack that supports the following operations in O(1) time: