Monotonic Stacks & Queues

A plain stack records history in last-in-first-out order; a monotonic stack records only the useful history. The rule is one extra line: before pushing a new element, pop every element already on the stack that would violate a chosen order, increasing or decreasing, and only then push. What survives on the stack is always a sorted sequence, and the elements you discard are discarded exactly when they stop being able to influence any future answer. That single discipline collapses a whole family of array questions (what is the next value to my right larger than me?, how far back is the last taller bar?, what is the maximum of every length-$k$ window?) from quadratic brute force to a single linear pass.¹

The questions all share a shape. For each index $i$ we want the nearest index to one side whose value beats $a[i]$ in some sense (greater, smaller). Brute force re-scans from every $i$ and costs $\Theta (n^2)$. The monotonic stack avoids the re-scan by carrying, at all times, precisely the set of indices whose answer is still unknown, discharging each one the instant its answer appears.

The monotonic stack: next greater element

The canonical task: for each $a[i]$, find $\text{nge}(i)$, the smallest $j>i$ with $a[j]>a[i]$ (or none). Scan left to right keeping a stack of indices whose next-greater is still unknown, maintained so their values are strictly decreasing from bottom to top. When we reach $a[i]$:

If $a[i]$ exceeds the value at the top, then $a[i]$ is the answer for that top index, the first larger value to its right, so we pop it, record $\text{nge}=i$, and repeat. We keep popping while $a[i]$ beats the new top; each popped index has just found its next-greater. Once the top is $\ge a[i]$ (order restored), we push $i$, still unresolved. Anything left on the stack at the end has no greater element to its right.

The body of the while looks as if it could be quadratic, but it is not.

The same scan, with the comparison flipped to $a[\text{top}(S)]>a[i]$ and a strictly-increasing stack, computes the next smaller element; reversing the scan direction gives previous greater / previous smaller. Four cousins, one template. Daily Temperatures is literally $\text{Next-Greater}$ returning $j-i$ instead of $j$; the classic stock span is previous-greater; and as we will see, trapping rain water is bounded on each side by the previous- and next-greater bars. They are all the same machine pointed in different directions.²

Largest rectangle in a histogram

Given bar heights $h[\mathrm{1..}n]$ of unit width, find the largest axis-aligned rectangle that fits under the skyline. The key observation: the maximal rectangle using bar $i$ as its limiting (shortest) height extends left until it hits the nearest shorter bar and right until the nearest shorter bar. So if $L(i)$ is the previous-smaller index and $R(i)$ the next-smaller index, bar $i$ contributes a rectangle of height $h[i]$ and width $R(i)-L(i)-1$, and the answer is the maximum of these over all $i$. That is two monotonic scans, and we can fuse them into one.

Keep an increasing stack of bar indices. When bar $i$ arrives shorter than the top, the top bar can extend no further right: $i$ is its next-smaller bar. Pop it. Its previous-smaller bar is exactly the new stack top after the pop, because the stack is increasing, so the element now exposed beneath it is the closest earlier bar shorter than the popped one. So at the moment of popping index $t$ with $i$ as the trigger:

where the width spans from just past the previous-smaller bar (the exposed stack top) up to just before the next-smaller bar $i$. Both boundaries are pinned to genuine smaller bars, so the rectangle is exactly the widest one of height $h[t]$.

When the trigger bar is shorter than several stacked bars, we pop them one after another, each discharged with its own correct width, before pushing the trigger. A sentinel of height $0$ appended at the end flushes everything still on the stack.

Every index is pushed once and popped once, so the histogram is solved in amortized $O(n)$ time and $O(n)$ space, by the same aggregate argument as before. What was a $\Theta (n^2)$ try every pair of boundaries search becomes a single sweep precisely because the increasing stack hands us both the left and right smaller-boundaries for free.

The monotonic deque: sliding-window maximum

Now stream the maximum of every contiguous sliding window of width $k$: $\max \{a[i],\dots ,a[i+k-1]\}$ for each start $i$. A binary heap of the current window gives $O(n\log k)$, since every slide does an insert and a (lazy) delete. A monotonic deque does it in $O(n)$.

Maintain a double-ended queue of indices whose values are strictly decreasing from front to back. Two rules per step at index $i$:

1. Push back, popping smaller tails. While the back's value is $\le a[i]$, pop it, since it can never again be a maximum: $a[i]$ is at least as large and stays in the window at least as long. Then push $i$ at the back.
2. Expire the front. If the front index has fallen out of the window ($\text{front}\le i-k$), pop it from the front.

After both rules, the front holds the index of the maximum of the current window: it is the largest value among all still-live candidates, because every larger-or-equal later value would have evicted it, and every earlier larger value that left the window was expired.

Each index enters the deque once (one push) and leaves once (one pop, from either end), so across the whole stream the deque does $O(n)$ work, independent of $k$. That beats the heap's $O(n\log k)$ and, unlike the heap, never carries stale elements, since out-of-window indices are expired from the front the moment they become irrelevant.³

Why one idea covers so many problems

Stock span, daily temperatures, largest rectangle, maximal rectangle in a binary matrix (a histogram per row), and trapping rain water are all the same previous/next-greater-or-smaller machinery. Trapping rain water, for instance, holds water above index $i$ up to $\min$ of the tallest bar to its left and the tallest bar to its right: two directional maxima that a monotonic stack supplies in one pass each. Once you recognize nearest element beating me on one side, the monotonic stack (or, for windowed maxima, the monotonic deque) is the reflex: one push and one pop per element, $O(n)$ total.

Takeaways

• A monotonic stack stays sorted by popping order-violating elements before each push; at every moment it holds exactly the indices whose answer is still unresolved.
• Next greater element is the core routine: a decreasing stack of indices, resolved when a larger value arrives. By an aggregate argument (each index pushed once, popped at most once) it runs in amortized $O(n)$.
• Largest rectangle in a histogram fuses a previous-smaller and a next-smaller scan into one increasing stack: a popped bar's left/right limits are the exposed stack top and the trigger index, both genuine smaller bars, so the linear sweep computes every maximal rectangle.
• A monotonic (decreasing) deque streams the sliding-window maximum in $O(n)$: push at the back popping smaller tails, expire the front when it leaves the window, and the front is always the window max, beating a heap's $O(n\log k)$.
• Daily temperatures, stock span, and trapping rain water are the same previous/next-greater machinery pointed in different directions.