Stacks, Queues & Heaps
Monotonic Stack
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
next greaternext smallerwarmer temperaturehistogramspannearest larger
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- “Next/previous greater or smaller element”?
- Largest rectangle / trapping water by bars?
- Maintain a stack that stays increasing or decreasing.
Classic problem
Daily Temperatures (LeetCode 739) — for each day, how many days until a warmer one. Keep a stack of indices with decreasing temperatures; a hotter day resolves everything cooler behind it.
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0] — day 2 (75°) waits 4 days until day 6 (76°).
Common pitfalls
Wrong monotonic direction (inc vs dec).
Storing values when you need indices (or vice-versa).