Max Stack

Hard

Design a stack that supports finding and removing the maximum element. Implement MaxStack() and: push(x), top() (returns the top element), pop() (removes and returns the top element), peekMax() (returns the maximum element), and popMax() (removes and returns the maximum element; if there are ties, remove the one closest to the top).

Example 1

Input:  operations = ["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"], values = [[],[5],[1],[5],[],[],[],[],[],[]]
Output: [null,null,null,null,5,5,1,5,1,5]

Constraints

• -10^7 <= x <= 10^7
• At most 10^4 calls.
• top, pop, peekMax, popMax are only called on a non-empty stack.