Max Stack

Design a stack supporting push, pop, top, peekMax, and popMax. All operations should be efficient.

Example 1

push(5), push(1), push(5), top()→5, popMax()→5, top()→1, peekMax()→5, pop()→1, top()→5

Solution Approach

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.

Java

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)