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 15 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
- Sliding Window Maximum Hard
- Maximal Rectangle Hard
- Remove K Digits Medium
- Remove Duplicate Letters Medium
- Sum of Subarray Ranges Medium
- Final Prices With a Special Discount in a Shop Easy
- Shortest Subarray with Sum at Least K Hard
- Create Maximum Number Hard
- Number of Visible People in a Queue Hard
- Online Stock Span Medium
- Using a Robot to Print the Lexicographically Smallest String Medium