Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Examples
Input: [["MinStack","push","push","push","getMin","pop","top","getMin"],[[],[-2],[0],[-3],[],[],[],[]]]
Output: [null,null,null,null,-3,null,0,-2]
Input: [["MinStack","push","push","top","getMin","pop","getMin"],[[],[5],[2],[],[],[],[]]]
Output: [null,null,null,2,2,null,5]
Hints
Use a single stack where each element is a tuple containing the value and the current minimum value up to that point.
When pushing a new value, compare it with the current minimum (top of the min stack) and push the smaller value onto the min stack.
Implement lazy removal by keeping track of the minimum value separately and only updating it when the current minimum is popped from the main stack.
Related Problems
Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.