Design a stack supporting push, pop, top, peekMax, and popMax. All operations should be efficient.
push(5), push(1), push(5), top()→5, popMax()→5, top()→1, peekMax()→5, pop()→1, top()→5
Use two stacks: main stack and max-tracking stack. For popMax, use a temp stack to find and remove the max.
- mainStack: all elements. maxStack: running max at each level.
- For pop: pop both stacks.
- For popMax: use temp stack to uncover the max element, then restore.
import java.util.*;
class MaxStack {
Deque<Integer> stack = new ArrayDeque<>(), 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: popMax: O(N); others O(1)
- Space Complexity: O(N)