visual walkthrough
Daily Temperatures
Next-greater distance; the most-asked monotonic-stack Medium.
The idea
Instead of every day searching ahead, let a warm day announce itself. Keep a stack of days that haven't seen a warmer day yet. When a warmer day arrives, it resolves every colder day on top of the stack at once.
The stack stays sorted (coldest on top), and each day is pushed and popped at most once.
Complexity
| approach | time | space |
|---|---|---|
| Look ahead for each day | O(n²) | O(1) |
| Monotonic stack | O(n) | O(n) |