Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the `MinStack` class: `push(val)` pushes the element onto the stack. `pop()` removes the element on the top of the stack. `top()` gets the top element of the stack. `getMin()` retrieves the minimum element in the stack. You must implement a solution with `O(1)` time complexity for each function.
Examples
Constraints
-2^31 <= val <= 2^31 - 1Methods pop, top and getMin operations will always be called on non-empty stacks.At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
Approach
Use two stacks: one for storing the actual values, and another for storing the minimum values. When pushing a value, we push it to the main stack. We also push it to the min stack if the min stack is empty or the new value is less than or equal to the current minimum. When popping, if the popped value from the main stack equals the top of the min stack, we pop from the min stack as well. The minimum value is always at the top of the min stack.
Complexity Analysis
This approach requires O(n) space for the extra stack in the worst case.
class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack;
public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); // Push to minStack if it's the new minimum if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { int val = stack.pop(); // Pop from minStack if the popped value is the minimum if (val == minStack.peek()) { minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); }}