Sign in to watch this lesson
Algorithms - Linear Data Structures · 4:28
Monotonic Stack
A stack that stays rising from bottom to top answers "nearest smaller to the left" for every element in one linear pass: each new bar knocks off the bars at least as tall, and whatever is left on top is its answer. We trace it on [3, 7, 8, 4, 2, 6, 5], cover the four variants and the tie rules, then let the same stack hand every bar of the histogram [2, 1, 5, 6, 2, 3] both of its boundaries to find the largest rectangle (10), and finish with the contribution technique for the sum of subarray minimums. Timings on this Mac compare the stack with the quadratic scans.
You will learn
- Find the nearest smaller (or greater) element to the left or right of every position in O(n) with a monotonic stack of indices
- Explain the amortised argument: every index is pushed once and popped at most once
- Compute the largest rectangle in a histogram as h * (R - L - 1) per bar, using a zero-height sentinel to flush the stack
- Use previous/next smaller boundaries to count subarrays (contribution technique), breaking ties with >= on one side and > on the other