1. One-Liner
A monotonic stack maintains strictly increasing or decreasing values (or indices) to answer nearest greater/smaller in amortized O(n).
2. The Problem It Solves
Powers largest rectangle in histogram, maximal rectangles, stock problems, and Cartesian tree construction ideas.
3. The Core Idea
When order breaks, pop and compute using popped bar as height bounded by new wall—histogram classic uses increasing stack with sentinel 0.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Iterate heights (+0 sentinel) |
| 2 | While top > current: pop height, width from new top to i |
| 3 | Update max area |
| 4 | Push index |
5. Dry Run Example
Heights [2,1,5,6,2,3]—pops determine rectangles when shorter bar arrives.
6. Key Properties
| Property | Detail |
|---|---|
| Variant | Next greater / smaller |
| Cartesian tree | Monotonic stack build |
| 2D | Extension with tricks |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| GIS / vision | Histograms |
| Finance | Range areas |
| Competitive | Classic template |
8. Interview Tips
Clarify increasing vs decreasing for the problem; sentinel avoids empty-stack checks.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Divide & conquer | O(n log n) area |
| Two-pointer | Not for general hist |
| Sparse table | RMQ different |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n) for histogram |
| Space | O(n) stack |
Implementation Example (PYTHON)
def largest_rect_hist(h):
st = []
best = 0
for i, x in enumerate(h + [0]):
while st and h[st[-1]] > x:
j = st.pop()
left = st[-1] if st else -1
best = max(best, h[j] * (i - left - 1))
st.append(i)
return best