Monotonic Stack problems, grouped by pattern
A monotonic stack keeps its items in increasing or decreasing order, popping anything that breaks the order. Each pop answers a question like "what is the next greater element?" for the item being removed, all in one pass.
When to reach for it
- Next greater or next smaller element
- How far until a warmer day, taller bar or higher price
- Largest rectangle or span problems
Mistakes to watch for
- Storing values when you need indices
- Choosing strict vs non-strict comparison for duplicates
- Forgetting the second pass for circular arrays
The 4 problems
1Monotonic Stack
- Next Greater Element I Animated Easy
- Daily Temperatures Animated Medium
- Next Greater Element II Animated Medium
- Largest Rectangle in Histogram Animated Hard