Practice/LinkedIn/Leetcode 716. Max Stack

Leetcode 716. Max Stack

CodingMust

Problem

Design a specialized stack data structure that supports standard stack operations plus the ability to efficiently retrieve and remove the maximum element. Your implementation must provide the following operations:

• push(x): Add an integer x to the top of the stack
• pop(): Remove and return the element at the top of the stack
• top(): Return the element at the top of the stack without removing it
• peekMax(): Return the maximum element in the stack without removing it
• popMax(): Remove and return the maximum element from the stack (if there are multiple instances of the maximum value, remove the most recently added one)

The key challenge is handling popMax() efficiently when the maximum element is not at the top of the stack. After removing the maximum, the relative order of remaining elements must be preserved.

Requirements

1. Implement all five operations: push, pop, top, peekMax, and popMax
2. When multiple elements have the maximum value, popMax must remove the most recently pushed one
3. Maintain the stack property (LIFO order) for regular pop operations
4. Handle edge cases such as empty stack operations appropriately

Constraints

• -10^7 ≤ x ≤ 10^7
• At most 10^4 calls will be made to each function
• Calls to pop, top, peekMax, and popMax will only be made when the stack is non-empty
• Optimize for practical performance across all operations

Examples

Example 1:

` Operations: push(5), push(1), push(5) Stack state: [5, 1, 5] (bottom to top)

top() → 5 (most recent element) popMax() → 5 (removes top 5, most recent max) top() → 1 (now top element) peekMax() → 5 (first 5 is still max) pop() → 1 (removes current top) top() → 5 (only element remaining) `

Example 2:

` Operations: push(3), push(7), push(2), push(7) Stack state: [3, 7, 2, 7] (bottom to top)

peekMax() → 7 (maximum value) popMax() → 7 (removes most recent 7) Stack state: [3, 7, 2] top() → 2 (top unchanged) popMax() → 7 (removes remaining 7) Stack state: [3, 2] `

Example 3:

` Operations: push(1), push(2), push(3), push(4) Stack state: [1, 2, 3, 4] (ascending order)

popMax() → 4 popMax() → 3 popMax() → 2 top() → 1 (only element left) `