Monotonic Stack
A monotonic stack keeps its elements in increasing or decreasing order and pops anything that breaks the order. Each pop tells you something useful, usually the next greater or smaller element for the value being removed, as in Daily Temperatures.
With 35 problems in four chapters, it is one of the shorter plans. It moves from the basic stack to Largest Rectangle in Histogram and its relatives, then to the contribution method for summing over all subarrays, and ends with building the lexicographically smallest result. It suits anyone who knows the idea but still stalls on the histogram problems.
Want company while you work through this list? Sign in, open the study room, and your heroine will bring you the problems one at a time.
I. Monotonic Stack
§1.1 Fundamentals
§1.2 Advanced (Optional)
II. Rectangles & Histograms
II. Rectangles & Histograms
| Problem | Rating |
|---|---|
| 84. Largest Rectangle in Histogram | 1900 |
| 85. Maximal Rectangle | 2100 |
| 221. Maximal Square | 1800 |
| 1504. Count Submatrices with All Ones | 1700 |
| 1277. Count Square Submatrices with All Ones | 1600 |
III. Contribution Method
III. Contribution Method
IV. Smallest Lexicographical Order
IV. Smallest Lexicographical Order
This is the third plan on Track 1; if you already know the pattern, mark it as done before when you sign your study contract and the route skips it.
Ratings come from zerotrac's LeetCode contest ratings. Some problems have no zerotrac rating and are marked Unrated.
Open the study room