Design a stack that supports push, pop, top, peekMax (retrieve max element), and popMax (pop the max element). Implement each operation.
push(5), push(1), push(5) → top()=5, popMax()=5, top()=1, peekMax()=5, pop()=1, top()=5
Use two stacks: one main stack and one maxStack tracking the current max at each level. For popMax, use a temp stack to pop elements until the max is found, then restore.
- Main stack: stores all elements.
- maxStack: at each push, push max(element, maxStack.top()).
- For pop: pop from both stacks.
- For popMax: use a temp stack to pop elements until main.top()==max, pop both, then push temp elements back.
import java.util.*;
class MaxStack {
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> maxStack = new ArrayDeque<>();
public void push(int x) {
stack.push(x);
maxStack.push(maxStack.isEmpty() ? x : Math.max(x, maxStack.peek()));
}
public int pop() {
maxStack.pop();
return stack.pop();
}
public int top() { return stack.peek(); }
public int peekMax() { return maxStack.peek(); }
public int popMax() {
int max = peekMax();
Deque<Integer> temp = new ArrayDeque<>();
while (top() != max) temp.push(pop());
pop();
while (!temp.isEmpty()) push(temp.pop());
return max;
}
}
- Time Complexity: O(N) for popMax, O(1) for others
- Space Complexity: O(N)