Min Stack
Design a class MinStack: a last-in, first-out collection of integers that can also report its smallest element instantly. push(val) adds val on top, pop() removes the top element, top() returns the top element without removing it, and getMin() returns the smallest element currently stored. pop, top and getMin are only called when at least one element is stored. Every operation must run in O(1) time, so scanning the elements inside getMin is not allowed.
Examples
MinStack(); push(-2); push(0); push(-3); getMin(); pop(); top(); getMin() returns -3, 0, -2
After the three pushes the smallest value is -3. pop() removes -3, which leaves 0 on top and makes -2 the smallest value again.
MinStack(); push(2); push(1); push(1); pop(); getMin() returns 1
Two copies of 1 are pushed. Popping one of them still leaves a 1 stored, so getMin() must return 1, not 2.
Constraints
- -2^31 <= val <= 2^31 - 1
- pop, top and getMin are only called when at least one element is stored.
- At most 3 * 10^4 calls will be made to push, pop, top and getMin.
Hints
A single 'current minimum' variable works until the minimum itself is popped. What would you need to have remembered to know the minimum of what remains?
Keep an auxiliary stack that records, for each element, the minimum of that element and everything below it.
On push(val), push val onto the main stack and min(val, current minimum) onto the min stack. On pop, pop both. top() reads the main stack and getMin() reads the min stack, each in O(1).
Drill This: Your Approach First
Approach
The minimum only changes when elements are pushed or popped at the top, so you can remember the minimum at every height. Keep a second stack in lockstep with the main one: each push also records min(val, previous minimum), and each pop removes from both. getMin just reads the top of the min stack. Every operation is O(1) time, and the extra stack costs O(n) space.
Time
O(1) per operation
Space
O(n)
Pitfall
Solutions
class MinStack {
private final Deque<Integer> stack = new ArrayDeque<>();
private final Deque<Integer> mins = new ArrayDeque<>();
public void push(int val) {
stack.push(val);
mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
}
public void pop() {
stack.pop();
mins.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return mins.peek();
}
}class MinStack:
def __init__(self):
self.stack = []
self.mins = []
def push(self, val: int) -> None:
self.stack.append(val)
self.mins.append(val if not self.mins else min(val, self.mins[-1]))
def pop(self) -> None:
self.stack.pop()
self.mins.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.mins[-1]