Practice/Snowflake/Leetcode 155. Min Stack

Leetcode 155. Min Stack

CodingMust

Problem

Implement a special stack data structure that supports standard stack operations along with retrieving the maximum element currently in the stack. All operations must execute in O(1) constant time complexity.

Your MaxStack class should support the following methods:

• push(x): Add element 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
• getMax(): Return the maximum element currently in the stack without removing it

The key challenge is efficiently tracking which element is the maximum as the stack contents change through push and pop operations.

Requirements

1. All operations must run in O(1) time complexity
2. The stack should handle negative numbers correctly
3. The stack should handle duplicate values
4. getMax() should always return the current maximum among all elements in the stack
5. After popping the maximum element, getMax() should correctly return the new maximum

Constraints

• -10^9 <= x <= 10^9 (element values)
• At most 10^4 calls will be made to each method
• pop(), top(), and getMax() will only be called when the stack is not empty
• All operations must complete in O(1) time

Examples

Example 1:

` Operations: ["MaxStack", "push", "push", "push", "getMax", "pop", "getMax"] Values: [[], [5], [1], [5], [], [], []] Output: [null, null, null, null, 5, 5, 5]

Explanation: MaxStack maxStack = new MaxStack(); maxStack.push(5); // stack is now [5] maxStack.push(1); // stack is now [5, 1] maxStack.push(5); // stack is now [5, 1, 5] maxStack.getMax(); // returns 5 maxStack.pop(); // returns 5, stack is now [5, 1] maxStack.getMax(); // returns 5 `

Example 2:

` Operations: ["MaxStack", "push", "push", "push", "getMax", "pop", "getMax"] Values: [[], [3], [7], [9], [], [], []] Output: [null, null, null, null, 9, 9, 7]

Explanation: After pushing 3, 7, and 9, the maximum is 9. After popping 9, the new maximum is 7. `