Max Stack

Max Stack is a LeetCode problem (716) commonly asked in LinkedIn interviews, requiring design of a stack with extra max-finding capabilities using structures like doubly linked lists and heaps or TreeMaps.[1][3]

Problem Statement

Design a MaxStack class supporting five operations:

• void push(int x): Pushes element x onto the stack.
• int pop(): Removes and returns the top element (standard stack pop).
• int top(): Returns the top element without removing it.
• int peekMax(): Returns the current maximum element in the stack.
• int popMax(): Removes and returns the current maximum element (not necessarily at the top; if ties exist, remove the most recently added one).[3][5][1]

Key Requirements

• All operations must be efficient, ideally amortized O(1) for push/pop/top and O(log n) for max operations.
• Handle duplicates: For popMax(), prioritize the most recent occurrence of the max value.[4][1]

Example Usage

MaxStack stack = new MaxStack(); stack.push(5); // stack: [5], max: 5 stack.push(1); // stack: [5,1], max: 5 stack.push(5); // stack: [5,1,5], max: 5 stack.top(); // returns 5 (top) stack.popMax(); // removes second 5, stack: [5,1], returns 5 stack.top(); // returns 1 stack.peekMax(); // returns 5 stack.pop(); // removes 1, stack: [5], returns 1

This matches the sequence shown in multiple sources, where after pushes, popMax() targets the latest 5.[8][1][4]

Constraints

• -1000 <= x <= 1000
• At most 10^4 calls to push/pop/top/peekMax/popMax.
• Implement in languages like Java/C++/Python, often using custom doubly linked list nodes plus a multiset or TreeMap<value, deque<node>> for O(1) deletions and O(log n) max access.[1][3]