Min Stack
Stacks & Queues: lesson 6 of 9
Carry the answer up with the data instead of recomputing it.
Lesson 6 of 9 · 5 min
Min Stack
Step 1 of 8
min()—
to push
5
2
7
1
valuesempty
minsempty
5
5
2
2
7
2
1
1
Two stacks that rise and fall together: the values, and the minimum so far at each level.
The Idea
A stack can hand back its top in O(1), but its minimum would need a scan. So record the minimum at push time, on a second stack that rises and falls with the first.
Pop both together and the old minimum reappears by itself — no recomputation, ever.
Real-World Example
A hiker noting, at every camp, the lowest altitude reached so far. Walking back down the same path, each note is still correct for that point; nobody re-measures the valley.
The Code
class MinStack:
def __init__(self): self.main, self.mins = [], []
def push(self, x):
self.main.append(x)
# the minimum of everything below, stored beside the value
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.main.pop()
def min(self): return self.mins[-1]
s = MinStack()
for x in [5, 2, 7, 1]: s.push(x)
print(s.min(), s.mins) # 1 [5, 2, 2, 1]
s.pop() # the 1 leaves
print(s.min()) # 2 -- the old minimum is simply back on topYour turn
What does this print?
mins = []
for x in [4, 6, 3, 9]:
mins.append(x if not mins else min(x, mins[-1]))
mins.pop()
print(mins)Mini quiz
1 / 3