Largest rectangle in histogram
StopStack
- CH1 i
38/38
Bars wait in rising order. A lower bar closes each taller one, whose rectangle reaches back to the bar under it.
Step through it →Monotonic Stack
A monotonic stack holds the items still waiting for an answer, in sorted order, and each new item pops every item it answers.
Daily temperatures: the wait for a warmer day
StopStack
temperatures
- CH1 i
answer starts as all zeros, and the stack of waiting days is empty.
Typical cost O(n) time, O(n) spaceFull lesson: Daily Temperatures →
When to reach for it
- You want each item's next greater or next smaller item.
- An item waits until a later one settles it: a warmer day, a lower bar.
- Once settled, an item never matters again.
- The brute force scans ahead from every item, which is O(n²).
What stays true
Before a day is pushed, it pops every colder day on top, so it always lands on one at least as warm. Each day is pushed once and popped at most once, so the scan is O(n).
The waiting days stay in order
StopStack
InvariantThe days on the stack get no warmer from bottom to top.✓ Holds
- CH1 i
answer starts as all zeros, and the stack of waiting days is empty.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Only a warmer day pops. Popping on ties would give the first three days a wait of 1, not 0.
Daily temperatures on the inputs that trip it up
StopStack
- CH1 i
answer starts as all zeros, and the stack of waiting days is empty.
Answer[0, 0, 0, 0]Steps13
Variants
Min stack
StopStack
- CH1 call
15/15
mins is a monotonic stack too: each entry is the smallest at or below its height.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Daily temperatures: the wait for a warmer day
StopStack
- CH1 i
answer starts as all zeros, and the stack of waiting days is empty.
daily_temperatures.py
def daily_temperatures(temperatures): answer = [0] * len(temperatures) stack = [] # days still waiting for a warmer one for i, t in enumerate(temperatures): while stack and temperatures[stack[-1]] < t: j = stack.pop() answer[j] = i - j stack.append(i) return answer