Monotonic Stack
Problems:
- https://leetcode.com/problems/maximal-rectangle/description/?envType=daily-question&envId=2026-01-11
https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2/
A monotonic stack is a special data structure used in algorithmic problem-solving. Monotonic Stack maintaining elements in either increasing or decreasing order.
Where it's used?
Commonly used in problems to find the next greater or smaller element in an array etc.
Ex: this Sum of Subarrray minimums problem https://leetcode.com/problems/sum-of-subarray-minimums/editorial/
It’s quite simple actually, for a monotonically increasing stack, only push values as it increases.
- it there are values smaller than the top of the stack, you pop from the stack until the value is greater than the current top of the stack, or if the stack is empty
“i also find the concept of a monotonically increasing stack confusing because we’re trying to keep the minimum so how like i always get confused with increasing or decreasing like for minimum i use an increasing and for decreasing it is a maximum maximize is that always the case”
Totally normal confusion. The trick is: the stack is monotonic in the VALUES it stores, and which direction you choose depends on what boundary you’re trying to find.
The reliable mental model
When you’re computing contributions, you usually want, for each a[i]:
- as a minimum: span until you hit something strictly smaller (or smaller/equal depending on ties)
- as a maximum: span until you hit something strictly larger (or larger/equal)
To get those spans in O(n), you keep a stack where values are ordered so that when a “ba