475. Max Stack
Design a MaxStack: a stack that, on top of the usual operations, can also report and remove its largest element.
Implement five methods:
push(x)— putxon top of the stack.pop()— remove the top element and return it.top()— return the top element without removing it.peek_max()— return the largest element currently in the stack.pop_max()— remove and return the largest element; if it occurs several times, remove the occurrence closest to the top.
Every call to pop, top, peek_max, and pop_max is guaranteed to happen while the stack is non-empty. Your program processes a sequence of these operations and prints the value returned by each one that returns something.
Can you support top in O(1) and everything else in O(log n)?
Example 1:
Input: push(5), push(1), push(5), top() → 5, popMax() → 5, top() → 1, peekMax() → 5, pop() → 1, top() → 5
Output: [5, 5, 1, 5, 1, 5]
Explanation: Stack grows to [5, 1, 5]. top sees 5. popMax removes the top 5 (the max occurrence nearest the top), leaving [5, 1]. Now top is 1, but peekMax still finds the bottom 5. pop removes the 1, and top is 5 again.
Example 2:
Input: push(1), push(5), push(3), push(5), peekMax() → 5, popMax() → 5, top() → 3, popMax() → 5, top() → 3, pop() → 3, top() → 1
Output: [5, 5, 3, 5, 3, 3, 1]
Explanation: With [1, 5, 3, 5], the first popMax removes the topmost 5, leaving [1, 5, 3]. The second popMax must dig out the 5 sitting **under** the 3 — the stack becomes [1, 3] with the 3 still on top.
Constraints:
- 1 ≤ q ≤ 10⁴
- -10⁹ ≤ X ≤ 10⁹
- pop, top, peekMax, and popMax are never called on an empty stack.
Hints:
A plain list already gives you push/pop/top in O(1). The hard part is popMax: the maximum can be buried anywhere, so removal from the middle must be cheap.
A doubly linked list allows O(1) removal of any node you hold a reference to. Pair it with a structure that can hand you 'the node holding the current max' fast.
Keep an ordered map (or max-heap with lazy deletion) from value → nodes holding it, newest last. popMax takes the newest node of the largest value — newest is exactly 'closest to the top'. When a heap entry's node was already unlinked by pop, just discard it and look again.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: push(5), push(1), push(5), top(), popMax(), top(), peekMax(), pop(), top()
Expected output: [5, 5, 1, 5, 1, 5]