Design MinStack
Design a stack that supports push, pop, top, and getMin operations. The getMin operation returns the minimum element in the stack. Implement the MinStack class.
Constraints:
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- 1 <= x <= 2^31 - 1
Examples:
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,0,0,-2]
Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Solutions
Two Stacks
We use two stacks, one for the actual elements and one for the minimum elements. When we push an element, we also push it to the minStack if it's smaller or equal to the current minimum. When we pop an element, we also pop it from the minStack if it's equal to the current minimum.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x:
int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self) -> None:
if self.stack:
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]Follow-up:
How would you implement the MinStack class using a single stack?
