186. Design Stack With Peek And Pop Maximum Element
Design Stack With Peek And Pop Maximum Element
Design a MaxStack data structure that works like a normal stack and also supports retrieving and removing the current maximum value.
The stack must support adding values, removing the top value, reading the top value, reading the maximum value, and removing the maximum value.
If the maximum value appears multiple times in the stack, popMax() must remove only the maximum value that is closest to the top of the stack.
Constructor and Method Signatures
MaxStack()
- Creates an empty max stack.
void push(int x)
- Pushes
x onto the top of the stack.
int pop()
- Removes the element from the top of the stack and returns it.
- This method will not be called when the stack is empty.
int top()
- Returns the element currently on the top of the stack without removing it.
- This method will not be called when the stack is empty.
int peekMax()
- Returns the maximum element currently present in the stack without removing it.
- This method will not be called when the stack is empty.
int popMax()
- Returns the maximum element currently present in the stack and removes it.
- If the maximum element appears more than once, remove only the one nearest to the top of the stack.
- This method will not be called when the stack is empty.
Parameters
x: The integer value to push onto the stack.
Constraints
-10,000,000 ≤ x ≤ 10,000,0001 ≤ number of operations ≤ 10,000pop(), top(), peekMax(), and popMax() will not be called when the stack is empty.- No parameter value will be
null.
Examples
Example 1
MaxStack stack = new MaxStack()
Creates an empty stack.
stack.push(x = 4)
Stack becomes [4].
stack.push(x = 2)
Stack becomes [4, 2].
stack.push(x = 4)
Stack becomes [4, 2, 4].
stack.top()
Output: 4
The top element is 4.
stack.popMax()
Output: 4
The maximum value is 4. There are two 4 values, so the top-most one is removed. Stack becomes [4, 2].
stack.top()
Output: 2
The current top element is 2.
stack.peekMax()
Output: 4
The maximum value still present in the stack is 4.
stack.pop()
Output: 2
The top element 2 is removed. Stack becomes [4].
stack.top()
Output: 4
The only remaining element is 4.
Example 2
MaxStack stack = new MaxStack()
Creates an empty stack.
stack.push(x = -3)
Stack becomes [-3].
stack.push(x = 10)
Stack becomes [-3, 10].
stack.push(x = 7)
Stack becomes [-3, 10, 7].
stack.peekMax()
Output: 10
The largest value in the stack is 10.
stack.popMax()
Output: 10
The maximum value 10 is removed. Stack becomes [-3, 7].
stack.top()
Output: 7
The top element is now 7.
stack.pop()
Output: 7
The top element 7 is removed. Stack becomes [-3].
stack.peekMax()
Output: -3
The only remaining value is also the maximum value.