---
title: Monotonic Stacks & Queues
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 3
order: 503
summary: |
  A **monotonic stack** keeps its contents sorted by popping every element that
  would break the order before each push — turning a family of "previous/next
  greater (or smaller) element" questions into a single $O(n)$ scan. We trace
  the next-greater-element routine push by push and prove its amortized bound,
  fuse two such scans to measure the **largest rectangle in a histogram** in
  linear time, extend the idea to a **monotonic deque** that streams the
  **sliding-window maximum** in $O(n)$, and use asymmetric tie-breaking to
  count **subarray minimums** without double-counting duplicates.
topics: [Array Techniques]
sources:
  - book: Skiena
    ref: "§3.2 — Stacks and Queues"
  - book: CLRS
    ref: "Ch. 16 — Amortized Analysis"
practice:
  - title: 'Daily Temperatures'
    slug: daily-temperatures
    difficulty: Medium
  - title: 'Next Greater Element II'
    slug: next-greater-element-ii
    difficulty: Medium
  - title: 'Largest Rectangle in Histogram'
    slug: largest-rectangle-in-histogram
    difficulty: Hard
  - title: 'Sliding Window Maximum'
    slug: sliding-window-maximum
    difficulty: Hard
  - title: 'Trapping Rain Water'
    slug: trapping-rain-water
    difficulty: Hard
---

A plain [stack](/algorithms/data-structures/elementary-structures) 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.[^skiena-sq]

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]$:

> **Invariant.** The stack holds indices $i_1 < i_2 < \cdots < i_m$, not yet
> resolved, with $a[i_1] > a[i_2] > \cdots > a[i_m]$. Every index _not_ on the
> stack has already been assigned its next-greater element.

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.

```algorithm
caption: $\textsc{Next-Greater}(a[1..n])$ — next strictly-greater element to the right
$S \gets$ empty stack of indices
for $i \gets 1$ to $n$ do
  while $S$ not empty and $a[\text{top}(S)] < a[i]$ do
    $j \gets \text{pop}(S)$
    $\text{nge}[j] \gets i$ // $a[i]$: $j$'s next-greater
  $\text{push}(S, i)$ // unresolved
while $S$ not empty do
  $\text{nge}[\text{pop}(S)] \gets \text{none}$ // no greater right
```

### The scan, push by push

Here is the complete run on $a = \langle 2, 5, 3, 1, 4 \rangle$. The stack is
written bottom to top; each entry is an index with its value in parentheses.

| $i$ | $a[i]$ | pops and assignments | stack after (bottom $\to$ top) |
|---|---|---|---|
| $1$ | $2$ | — | $1\,(2)$ |
| $2$ | $5$ | pop $1$: $\text{nge}[1] = 2$ | $2\,(5)$ |
| $3$ | $3$ | — | $2\,(5),\ 3\,(3)$ |
| $4$ | $1$ | — | $2\,(5),\ 3\,(3),\ 4\,(1)$ |
| $5$ | $4$ | pop $4$: $\text{nge}[4] = 5$; then pop $3$: $\text{nge}[3] = 5$ | $2\,(5),\ 5\,(4)$ |
| end | — | pop $5$, then $2$: $\text{nge} = \text{none}$ | $\varnothing$ |

Read each row against the invariant: the value column of the stack is strictly
decreasing at every moment ($5, 3, 1$ before step $5$; then $5, 4$ after). Step
$5$ shows the payoff. The arrival of $4$ resolves two waiting
indices at once: value $1$ (index $4$) and value $3$ (index $3$) both see their
first larger value to the right, in that order, top of stack first. Then $5 \ge
4$ blocks further popping — value $5$ may yet be the next-greater of something
later, and $4$ itself now waits beneath it. Indices $2$ and $5$ survive to the
end and get $\text{none}$: nothing to their right ever beat them.

$$
% caption: Next-greater scan on $a=\langle 2,5,3,1,4\rangle$ at the decisive step.
%          Arriving $a[5]{=}4$ pops indices $4$ then $3$ (values $1,3$ both $<4$),
%          assigning $\text{nge}[4]{=}\text{nge}[3]{=}5$; index $2$ (value $5\ge4$)
%          survives, then $5$ is pushed
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!15] (4.4,-0.4) rectangle (5.1,0.4);
  \foreach \i/\v in {1/2,2/5,3/3,4/1,5/4} {
    \node[draw, minimum size=8mm, inner sep=1pt] (a\i) at (\i*0.95,0) {$\v$};
    \node[font=\footnotesize] at (\i*0.95,0.6) {\i};
  }
  \node[draw=acc, very thick, minimum size=8mm, inner sep=1pt] at (4.75,0) {};
  \node[font=\footnotesize, acc] at (4.75,1.1) {trigger $i{=}5$};
  \node[font=\footnotesize] at (0.0,-1.6) {stack};
  \node[draw, minimum size=7mm, inner sep=1pt] (sb) at (1.0,-1.6) {$2$};
  \node[draw, minimum size=7mm, inner sep=1pt] (sm) at (1.8,-1.6) {$3$};
  \node[draw, minimum size=7mm, inner sep=1pt] (st) at (2.6,-1.6) {$4$};
  \node[font=\footnotesize] at (1.0,-2.2) {$v{=}5$};
  \node[font=\footnotesize] at (1.8,-2.2) {$v{=}3$};
  \node[font=\footnotesize] at (2.6,-2.2) {$v{=}1$};
  \draw[->, red!75!black, thick] (st.east) .. controls (3.5,-1.55) and (4.85,-1.35) .. (4.9,-0.5);
  \draw[->, red!75!black, thick] (sm.north) .. controls (1.85,-0.95) and (4.0,-0.9) .. (4.55,-0.48);
  \node[font=\footnotesize, red!75!black] at (4.2,-1.9) {pop 4, then 3};
  \node[font=\footnotesize] at (1.0,-2.8) {bottom};
  \node[font=\footnotesize] at (2.6,-2.8) {top};
\end{tikzpicture}
$$

$$
% caption: Filmstrip of the same scan: stack contents (values, bottom to top) after
%          each index is processed; the gray tag left of each cell is the stored
%          index. Every element is pushed once and popped at most once — indices
%          $2$ and $5$ survive to the end with no greater element to their right
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \node[acc] at (0,2.5) {i = 1};
  \node[draw, minimum size=7mm, inner sep=1pt] at (0,0.35) {$2$};
  \node[font=\scriptsize, black, anchor=east] at (-0.42,0.35) {1};
  \node[black] at (0,-0.55) {push 2};
  \node[acc] at (2.15,2.5) {i = 2};
  \node[draw, minimum size=7mm, inner sep=1pt] at (2.15,0.35) {$5$};
  \node[font=\scriptsize, black, anchor=east] at (1.73,0.35) {2};
  \node[red!75!black] at (2.15,-0.55) {5 pops 2};
  \node[acc] at (4.3,2.5) {i = 3};
  \node[draw, minimum size=7mm, inner sep=1pt] at (4.3,0.35) {$5$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (4.3,1.05) {$3$};
  \node[font=\scriptsize, black, anchor=east] at (3.88,0.35) {2};
  \node[font=\scriptsize, black, anchor=east] at (3.88,1.05) {3};
  \node[black] at (4.3,-0.55) {push 3};
  \node[acc] at (6.45,2.5) {i = 4};
  \node[draw, minimum size=7mm, inner sep=1pt] at (6.45,0.35) {$5$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (6.45,1.05) {$3$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (6.45,1.75) {$1$};
  \node[font=\scriptsize, black, anchor=east] at (6.03,0.35) {2};
  \node[font=\scriptsize, black, anchor=east] at (6.03,1.05) {3};
  \node[font=\scriptsize, black, anchor=east] at (6.03,1.75) {4};
  \node[black] at (6.45,-0.55) {push 1};
  \node[acc] at (8.6,2.5) {i = 5};
  \node[draw, minimum size=7mm, inner sep=1pt] at (8.6,0.35) {$5$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (8.6,1.05) {$4$};
  \node[font=\scriptsize, black, anchor=east] at (8.18,0.35) {2};
  \node[font=\scriptsize, black, anchor=east] at (8.18,1.05) {5};
  \node[red!75!black] at (8.6,-0.55) {4 pops 1, 3};
  \draw[black] (1.08,-0.8) -- (1.08,2.7);
  \draw[black] (3.23,-0.8) -- (3.23,2.7);
  \draw[black] (5.38,-0.8) -- (5.38,2.7);
  \draw[black] (7.53,-0.8) -- (7.53,2.7);
\end{tikzpicture}
$$

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

> **Lemma (amortized $O(n)$).** $\textsc{Next-Greater}$ runs in $O(n)$ time.
>

> **Proof (aggregate).** Each index is **pushed exactly once**, in the single
> `push` at the end of the loop body, and is **popped at most once**, after which
> it never returns to the stack. A `while`-iteration performs one pop, so the
> total number of `while`-iterations across the whole run is at most $n$. The
> outer loop runs $n$ times and does $O(1)$ work besides popping. Total work is
> therefore $O(n) + O(n) = O(n)$, even though an individual step may pop many
> elements. $\qed$

The same bound falls out of the potential method with $\Phi = $ stack size: an
iteration that pops $k$ elements costs $k + O(1)$ real work but decreases the
potential by $k - 1$, so its [amortized](/algorithms/foundations/amortized-analysis)
cost is $O(1)$. Either way, the expensive steps are expensive precisely because
many earlier steps were cheap — the trace above pays for step $5$'s double pop
with the pushes at steps $3$ and $4$.[^clrs-amortized]

### Strictness, and the four cousins

The pop condition $a[\text{top}] < a[i]$ is **strict**, so equal values do not
resolve each other: on $a = \langle 3, 3, 5 \rangle$ the second $3$ does not pop
the first — both wait, stacked, until $5$ discharges them together. That is the
right behavior for "next _strictly_ greater". If the task is "next greater **or
equal**", pop on $a[\text{top}] \le a[i]$ instead. One comparison character
changes which of the two $3$s answers for which subarrays, and the section on
[counting subarray minimums](#counting-with-spans-sum-of-subarray-minimums)
shows why that choice is sometimes forced.

Flipping the comparison to $a[\text{top}] > a[i]$, with a strictly-increasing
stack, computes the **next smaller** element; reversing the scan direction gives
**previous greater / previous smaller**. Better still, the previous-side answers
come for free in the _same_ pass: at the moment $i$ is pushed, the element just
beneath it is the nearest earlier index that survived the pops — with pop-on-$<$
that is the previous greater-**or-equal** element, and with pop-on-$\le$ it is
the previous _strictly_ greater. Popping resolves the next side; pushing reads
off the previous side, with the strictness complemented. Four cousins, one
template. **Daily Temperatures** is literally $\textsc{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.

For a circular array (**Next Greater Element II**), run the identical scan over
$i = 1, \ldots, 2n$, comparing against $a[((i-1) \bmod n) + 1]$ but pushing only
while $i \le n$: the first pass builds the stack, the second lap only resolves
the leftovers that needed to wrap around.

::impl{algo="next_greater_element,daily_temperatures"}

## Largest rectangle in a histogram

Given bar heights $h[1..n]$ of unit width, find the largest axis-aligned
rectangle that fits under the skyline. 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:

$$
\text{area} = h[t] \cdot \parens{i - \text{(new top)} - 1},
$$

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 the widest one of height $h[t]$.

$$
% caption: Largest rectangle via a monotonic increasing stack: bar 5 triggers the pops;
%          the maximal rectangle of height $2$ spans bars 1–4 for area $8$
\begin{tikzpicture}[>=stealth, x=8mm, y=8mm]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (0,0) -- (7.4,0);
  \fill[acc, opacity=0.18] (0,0) rectangle (4,2);
  \draw[acc, thick] (0,0) rectangle (4,2);
  \draw (0,0) rectangle (1,3);
  \draw (1,0) rectangle (2,2);
  \draw (2,0) rectangle (3,4);
  \draw (3,0) rectangle (4,5);
  \draw[acc, very thick] (4,0) rectangle (5,1);
  \node[font=\footnotesize] at (0.5,-0.4) {$1$};
  \node[font=\footnotesize] at (1.5,-0.4) {$2$};
  \node[font=\footnotesize] at (2.5,-0.4) {$3$};
  \node[font=\footnotesize] at (3.5,-0.4) {$4$};
  \node[font=\footnotesize, acc] at (4.5,-0.4) {$5$};
  \node[font=\footnotesize, acc] at (4.75,1.35) {trigger};
  \node[font=\footnotesize, acc, fill=white, inner sep=1.5pt] at (2.0,2.35) {max area = 8};
\end{tikzpicture}
$$

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. The sentinel is a correctness requirement: bars
still on the stack after $i = n$ have no shorter bar to their right, so their
rectangles run to the array boundary — a height-$0$ bar at position $n+1$ is
shorter than every real bar and discharges each of them with $R = n + 1$.
Without it, a strictly increasing histogram would trigger no pops at all and
report $0$.

```algorithm
caption: $\textsc{Largest-Rectangle}(h[1..n])$ — fused previous/next-smaller scan
$S \gets$ empty stack of indices; append sentinel $h[n+1] \gets 0$
$\text{best} \gets 0$
for $i \gets 1$ to $n+1$ do
  while $S$ not empty and $h[\text{top}(S)] \ge h[i]$ do
    $t \gets \text{pop}(S)$
    $L \gets$ ($S$ empty $?$ $0$ $:$ $\text{top}(S)$) // previous-smaller bar
    $\text{best} \gets \max(\text{best},\; h[t] \cdot (i - L - 1))$
  $\text{push}(S, i)$
return $\text{best}$
```

### The whole computation, worked

Take $h = \langle 3, 2, 4, 5, 1 \rangle$, the skyline in the figures, with the
sentinel $h[6] = 0$ appended.

| $i$ | $h[i]$ | pops: $t$, $L$, $h[t] \cdot (i - L - 1)$ | stack after | best |
|---|---|---|---|---|
| $1$ | $3$ | — | $1$ | $0$ |
| $2$ | $2$ | $t{=}1$, $L{=}0$: $3 \cdot (2 - 0 - 1) = 3$ | $2$ | $3$ |
| $3$ | $4$ | — | $2, 3$ | $3$ |
| $4$ | $5$ | — | $2, 3, 4$ | $3$ |
| $5$ | $1$ | $t{=}4$, $L{=}3$: $5 \cdot 1 = 5$; $\;t{=}3$, $L{=}2$: $4 \cdot 2 = 8$; $\;t{=}2$, $L{=}0$: $2 \cdot 4 = 8$ | $5$ | $8$ |
| $6$ | $0$ | $t{=}5$, $L{=}0$: $1 \cdot (6 - 0 - 1) = 5$ | $6$ | $8$ |

Step $5$ carries the whole argument. Bar $5$ (height $1$) is shorter than the
entire stacked run $2, 4, 5$, so three rectangles are measured in sequence, each
with its exact left boundary read off the stack _after_ its pop: bar $4$ alone
($5 \times 1 = 5$, hemmed in by bar $3$ on the left), bars $3$–$4$ at height $4$
($4 \times 2 = 8$), and bars $1$–$4$ at height $2$ ($2 \times 4 = 8$ — the stack
is empty after popping index $2$, so the rectangle runs all the way to the left
edge, $L = 0$). The best, $8$, is achieved twice with different shapes. The
sentinel's only job here is bar $5$ itself, which extends the full width for
$1 \cdot 5 = 5$.

$$
% caption: The pop sequence at trigger $i{=}5$ on $h=\langle 3,2,4,5,1\rangle$: each pop
%          measures the widest rectangle whose limiting bar is the popped one. Left
%          boundary: the stack top exposed by the pop; right boundary: the trigger
\begin{tikzpicture}[>=stealth, font=\footnotesize, x=5mm, y=3.4mm]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!18] (3,0) rectangle (4,5);
  \draw[black] (0,0) rectangle (1,3);
  \draw[black] (1,0) rectangle (2,2);
  \draw[black] (2,0) rectangle (3,4);
  \draw[acc, thick] (3,0) rectangle (4,5);
  \draw[acc, thick] (4,0) rectangle (5,1);
  \draw[thick] (-0.2,0) -- (5.4,0);
  \foreach \x/\n in {0.5/1,1.5/2,2.5/3,3.5/4,4.5/5} {
    \node[font=\scriptsize, black] at (\x,-0.9) {\n};
  }
  \node at (2.5,-2.4) {pop bar 4 (h = 5)};
  \node[font=\scriptsize] at (2.5,-3.9) {w = 5 - 3 - 1 = 1, area 5};
  \fill[acc!18] (9.4,0) rectangle (11.4,4);
  \draw[black] (7.4,0) rectangle (8.4,3);
  \draw[black] (8.4,0) rectangle (9.4,2);
  \draw[black] (10.4,0) rectangle (11.4,5);
  \draw[acc, thick] (9.4,0) rectangle (11.4,4);
  \draw[acc, thick] (11.4,0) rectangle (12.4,1);
  \draw[thick] (7.2,0) -- (12.8,0);
  \foreach \x/\n in {7.9/1,8.9/2,9.9/3,10.9/4,11.9/5} {
    \node[font=\scriptsize, black] at (\x,-0.9) {\n};
  }
  \node at (9.9,-2.4) {pop bar 3 (h = 4)};
  \node[font=\scriptsize] at (9.9,-3.9) {w = 5 - 2 - 1 = 2, area 8};
  \fill[acc!18] (14.8,0) rectangle (18.8,2);
  \draw[black] (14.8,0) rectangle (15.8,3);
  \draw[black] (15.8,0) rectangle (16.8,2);
  \draw[black] (16.8,0) rectangle (17.8,4);
  \draw[black] (17.8,0) rectangle (18.8,5);
  \draw[acc, thick] (14.8,0) rectangle (18.8,2);
  \draw[acc, thick] (18.8,0) rectangle (19.8,1);
  \draw[thick] (14.6,0) -- (20.2,0);
  \foreach \x/\n in {15.3/1,16.3/2,17.3/3,18.3/4,19.3/5} {
    \node[font=\scriptsize, black] at (\x,-0.9) {\n};
  }
  \node at (17.3,-2.4) {pop bar 2 (h = 2)};
  \node[font=\scriptsize] at (17.3,-3.9) {w = 5 - 0 - 1 = 4, area 8};
\end{tikzpicture}
$$

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 because the increasing stack hands us both the left and
right smaller-boundaries for free.

Equal heights deserve a look. The pop condition is $h[\text{top}] \ge h[i]$
(non-strict), so an arriving bar pops earlier bars _of the same height_. On
$h = \langle 2, 2 \rangle$ plus sentinel: $i = 2$ pops bar $1$ and records
$2 \cdot (2 - 0 - 1) = 2$, understating that bar's true reach; then the sentinel
pops bar $2$ with the stack empty and records $2 \cdot (3 - 0 - 1) = 4$, the
correct answer. The pattern is general: within a run of equal-height bars, every
bar but the last gets a truncated width, and the last one measures the full
rectangle. The _maximum_ is therefore always right, even though the per-bar
widths are not — a distinction that matters the moment you need each bar's exact
span, as in the counting problems below.

::impl{algo="largest_rectangle_histogram"}

## The monotonic deque: sliding-window maximum

Now stream the maximum of every contiguous
[sliding window](/algorithms/sequences/two-pointers-and-windows) of width $k$:
$\max\{a[i], \ldots, a[i+k-1]\}$ for each start $i$. A binary
[heap](/algorithms/sorting/heaps-and-heapsort) 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.

> **Invariant (deque front is the window max).** After both rules at index $i$, the
> deque's 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 (rule 1), and every earlier larger value that
> left the window was expired (rule 2).

$$
% caption: Sliding-window maximum with a decreasing deque; window $[l,r]$ over $a$, deque
%          front (in accent) is the window max
\begin{tikzpicture}[>=stealth, x=9mm, y=9mm]
  \definecolor{acc}{HTML}{2348F2}
  % array row: values 1 3 5 2 4 6  ; window [3,5] = indices covering 5 2 4
  \foreach \i/\v in {1/1,2/3,3/5,4/2,5/4,6/6} {
    \node[draw, minimum size=8mm, font=\small] (a\i) at (\i,0) {$\v$};
    \node[font=\footnotesize\itshape] at (\i,0.72) {\i};
  }
  % window box over indices 3,4,5
  \draw[acc, thick] (2.5,-0.5) rectangle (5.5,0.5);
  \node[font=\footnotesize, acc] at (4,1.1) {windo\/w [l, r] = [3, 5]};
  % deque below: decreasing values 5 (idx3), 4 (idx5)
  \node[font=\footnotesize] at (-0.2,-1.5) {deque:};
  \node[draw=acc, thick, fill=acc!15, minimum size=8mm, font=\small] (d1) at (1.1,-1.5) {$5$};
  \node[draw, minimum size=8mm, font=\small] (d2) at (2.2,-1.5) {$4$};
  \node[font=\footnotesize, acc] at (1.1,-2.15) {front};
  \node[font=\footnotesize, acc] at (1.1,-2.72) {(max)};
  \node[font=\footnotesize] at (2.2,-2.15) {back};
  \node[font=\footnotesize] at (1.1,-0.78) {idx 3};
  \node[font=\footnotesize] at (2.2,-0.78) {idx 5};
  % index 4 (value 2) was popped from the back when 4 arrived
\end{tikzpicture}
$$

### A full stream

The run on $a = \langle 1, 3, 5, 2, 4, 6 \rangle$ with $k = 3$; deque entries
are index (value), front first, and the first output appears once the window is
full at $i = 3$.

| $i$ | $a[i]$ | back pops (rule 1) | expiry (rule 2) | deque after (front $\to$ back) | window: max |
|---|---|---|---|---|---|
| $1$ | $1$ | — | — | $1\,(1)$ | — |
| $2$ | $3$ | pop $1\,(1)$ | — | $2\,(3)$ | — |
| $3$ | $5$ | pop $2\,(3)$ | — | $3\,(5)$ | $[1,3]$: $5$ |
| $4$ | $2$ | — | — | $3\,(5),\ 4\,(2)$ | $[2,4]$: $5$ |
| $5$ | $4$ | pop $4\,(2)$ | — | $3\,(5),\ 5\,(4)$ | $[3,5]$: $5$ |
| $6$ | $6$ | pop $5\,(4)$, then $3\,(5)$ | — | $6\,(6)$ | $[4,6]$: $6$ |

Index $3$ (value $5$) fronts three consecutive
windows while smaller values come and go behind it — $2$ arrives and queues up
(it would be the max if $5$ expired), then $4$ evicts $2$ and queues up itself.
At $i = 6$ the value $6$ clears the whole deque from the back before $5$ ever
ages out. The deque always reads strictly decreasing left to right, and its
front is the answer.

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.[^skiena-deque]

::impl{algo="sliding_window_maximum"}

> **Intuition.** The deque is a monotonic _stack with a second exit_. Rule 1 is
> the monotonic-stack push (smaller elements can never win once a bigger,
> longer-lived one arrives); the extra front exit is what makes it a queue,
> discarding candidates that age out of the window rather than that get
> out-valued.

$$
% caption: Deque step at $i{=}6$ ($a[6]{=}6$) on $a=\langle 1,3,5,2,4,6\rangle$. The
%          incoming $6$ exceeds both tails, so back-popping clears indices $5,3$ (values
%          $4,5$); the deque collapses to $\langle 6\rangle$, the new window-$[4,6]$
%          maximum
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\footnotesize] at (-1.4,0) {before:};
  \node[draw, minimum size=8mm, inner sep=1pt] (b1) at (0,0) {$5$};
  \node[draw, minimum size=8mm, inner sep=1pt] (b2) at (0.95,0) {$4$};
  \node[font=\footnotesize] at (0,0.6) {idx 3};
  \node[font=\footnotesize] at (0.95,0.6) {idx 5};
  \node[font=\footnotesize] at (0,-0.62) {front};
  \node[font=\footnotesize] at (0.95,-0.62) {back};
  \node[draw=acc, very thick, minimum size=8mm, inner sep=1pt] (inc) at (2.9,0) {$6$};
  \node[font=\footnotesize, acc] at (2.9,0.62) {$a[6]$};
  \draw[->, red!75!black, thick] (2.45,0) -- (1.55,0);
  \node[font=\footnotesize, red!75!black] at (2.0,0.42) {pop 4, 5};
  \node[font=\footnotesize] at (-1.4,-1.7) {after:};
  \node[draw=acc, very thick, fill=acc!15, minimum size=8mm, inner sep=1pt] (af) at (0,-1.7) {$6$};
  \node[font=\footnotesize] at (0,-2.32) {idx 6};
  \node[font=\footnotesize, acc] at (1.95,-1.7) {front = windo\/w max = 6};
\end{tikzpicture}
$$

### When the front ages out

In the trace above, rule 2 never fired: every candidate was out-valued from the
back before it could grow stale. The opposite happens on descending input. Run
$a = \langle 6, 4, 3, 2, 5, 1 \rangle$ with $k = 3$: nothing pops from the back
during the descent $6, 4, 3, 2$, so the deque fills up with the whole run — each
value is a live candidate, since all the larger ones ahead of it will expire
first. At $i = 4$ the front index $1$ satisfies $1 \le 4 - 3$, so $6$ is expired
by _age_, not by value, and the reported max steps down to $4$. Then $5$ arrives
and clears the entire remainder from the back in one burst.

$$
% caption: Deque states on $a=\langle 6,4,3,2,5,1\rangle$, $k{=}3$ (front on top; gray
%          tags are indices; accent cell is the reported max once the window is full).
%          At $i{=}4$ the front expires by age ($6$ leaves though it is still the largest
%          value seen); at $i{=}5$ the arrival of $5$ clears the whole deque by value
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\v in {1/6,2/4,3/3,4/2,5/5,6/1} {
    \node[draw, minimum size=7mm, inner sep=1pt] at (\i*1.9,0) {$\v$};
    \node[font=\scriptsize, black] at (\i*1.9,0.55) {\i};
  }
  \node[black, anchor=east] at (0.9,0) {a:};
  \node[black, anchor=east] at (0.9,-1.1) {deque:};
  \node[draw, minimum size=7mm, inner sep=1pt] at (1.9,-1.1) {$6$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (3.8,-1.1) {$6$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (3.8,-1.8) {$4$};
  \node[draw=acc, thick, fill=acc!15, minimum size=7mm, inner sep=1pt] at (5.7,-1.1) {$6$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (5.7,-1.8) {$4$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (5.7,-2.5) {$3$};
  \node[draw=acc, thick, fill=acc!15, minimum size=7mm, inner sep=1pt] at (7.6,-1.1) {$4$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (7.6,-1.8) {$3$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (7.6,-2.5) {$2$};
  \node[draw=acc, thick, fill=acc!15, minimum size=7mm, inner sep=1pt] at (9.5,-1.1) {$5$};
  \node[draw=acc, thick, fill=acc!15, minimum size=7mm, inner sep=1pt] at (11.4,-1.1) {$5$};
  \node[draw, minimum size=7mm, inner sep=1pt] at (11.4,-1.8) {$1$};
  \node[red!75!black, font=\scriptsize] at (7.6,-3.2) {expire 6};
  \node[red!75!black, font=\scriptsize] at (9.5,-3.2) {pop 2, 3, 4};
  \node[black, anchor=east] at (0.9,-4.0) {max:};
  \node[black] at (1.9,-4.0) {-};
  \node[black] at (3.8,-4.0) {-};
  \node[acc] at (5.7,-4.0) {6};
  \node[acc] at (7.6,-4.0) {4};
  \node[acc] at (9.5,-4.0) {5};
  \node[acc] at (11.4,-4.0) {5};
\end{tikzpicture}
$$

Ties again hide a decision. Rule 1 pops while the back is $\le a[i]$, equal
values included, and deliberately so: the newer of two equal values survives at
least as long in the window, so the older one is dominated and can go. Popping
on $<$ instead, keeping equal values queued, still reports correct maxima — it
just lets the deque carry duplicates it will never need. The choice becomes
visible only when the problem asks _which index_ achieves the maximum: $\le$
reports the latest tied index, $<$ the earliest.

## Counting with spans: sum of subarray minimums

The same previous/next-smaller machinery solves an entirely different-looking
problem: compute $\sum \min(a[i..j])$ over all $\binom{n+1}{2}$ subarrays.
Summing subarray by subarray is $\Theta(n^2)$ at best. Instead, flip the
accounting to count **contributions**: each position $i$ contributes
$a[i] \cdot c_i$, where $c_i$ is the number of subarrays whose minimum is
_the element at_ $i$. A subarray has $a[i]$ as its minimum exactly when it
contains $i$ and stays strictly inside the region where $a[i]$ is smallest, so
$c_i$ is a product of two span lengths:

$$
c_i = \underbrace{(i - P(i))}_{\text{left choices}} \cdot
      \underbrace{(N(i) - i)}_{\text{right choices}},
$$

where $P(i)$ is the nearest index to the left with a value **strictly smaller**
than $a[i]$ (or $0$), and $N(i)$ the nearest index to the right with a value
**smaller or equal** (or $n+1$). The subarray's left end can sit anywhere in
$(P(i), i]$ and its right end anywhere in $[i, N(i))$, independently. Both span
arrays are single monotonic-stack passes, so the whole sum is $O(n)$.

On $a = \langle 3, 1, 2, 4 \rangle$:

| $i$ | $a[i]$ | $P(i)$ | $N(i)$ | left $\cdot$ right | contribution |
|---|---|---|---|---|---|
| $1$ | $3$ | $0$ | $2$ | $1 \cdot 1$ | $3$ |
| $2$ | $1$ | $0$ | $5$ | $2 \cdot 3$ | $6$ |
| $3$ | $2$ | $2$ | $5$ | $1 \cdot 2$ | $4$ |
| $4$ | $4$ | $3$ | $5$ | $1 \cdot 1$ | $4$ |

Total $17$, which matches brute force: the ten subarrays have minimums
$3, 1, 2, 4, 1, 1, 2, 1, 1, 1$, summing to $17$. Position $2$ dominates because
value $1$ is the minimum of every subarray containing it: $2$ choices of left
end times $3$ choices of right end.

The asymmetry — strict on the left, non-strict on the right — is what makes the
count exact in the presence of duplicates. Take $a = \langle 1, 1 \rangle$,
whose three subarrays ($[1..1]$, $[2..2]$, $[1..2]$) all have minimum $1$, for a
sum of $3$. With
the asymmetric rule, position $1$ gets $N(1) = 2$ (the equal value counts as a
right boundary) so $c_1 = 1 \cdot 1 = 1$, and position $2$ gets $P(2) = 0$ (the
equal value does not count as a left boundary) so $c_2 = 2 \cdot 1 = 2$; total
$3$. Make both sides strict and both positions claim the subarray $[1..2]$:
$c_1 = 1 \cdot 2$, $c_2 = 2 \cdot 1$, total $4$ — double-counted. Make both
sides non-strict and neither claims it: total $2$ — missed. The asymmetric rule
assigns every subarray's minimum to exactly one position, the _rightmost_
occurrence of the minimal value inside it.

> **Takeaway.** When equal values exist and each subarray must be counted once,
> break ties by strictness asymmetry: strict comparison on one side, non-strict
> on the other. The fused histogram scan already does this — pop on
> $h[\text{top}] \ge h[i]$ makes $R$ non-strict while the exposed stack top is a
> strictly smaller bar — which is why equal-height runs never
> double-measure their shared rectangle.

The identical pattern with comparisons flipped computes the sum of subarray
**maximums**, and the difference of the two sums answers "sum of (max $-$ min)
over all subarrays" in one linear pass each.

## 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 a problem reduces to "nearest element on one side beating
the current one," use the monotonic stack (or, for windowed maxima, the
monotonic deque): one push and one pop per element, $O(n)$ total.

$$
% caption: Trapping rain water: above each bar the water rises to
%          $\min(\text{leftMax},\text{rightMax})$, so the trapped height at index $i$ is
%          $\min(L_i,R_i)-h[i]$ — bounded on each side by a previous/next taller bar
\begin{tikzpicture}[>=stealth, x=7mm, y=7mm]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.4,-1.0) rectangle (8.2,4.3);
  % heights h = [3,0,2,0,4,1,2,3]
  % water fills to min(leftMax,rightMax) per column up to the cap
  \fill[acc!18] (1,0) rectangle (2,3);   % col1 h0 level3
  \fill[acc!18] (2,2) rectangle (3,3);   % col2 h2 level3
  \fill[acc!18] (3,0) rectangle (4,3);   % col3 h0 level3
  \fill[acc!18] (5,1) rectangle (6,3);   % col5 h1 level3
  \fill[acc!18] (6,2) rectangle (7,3);   % col6 h2 level3
  % bars h
  \foreach \i/\h in {0/3,1/0,2/2,3/0,4/4,5/1,6/2,7/3} {
    \ifnum\h>0 \draw[black, thick] (\i,0) rectangle (\i+1,\h);\fi
  }
  \draw[thick] (0,0) -- (8,0);
  % water level line at y=3, broken around the taller bar 4
  \draw[acc, dashed, thick] (1,3) -- (4,3);
  \draw[acc, dashed, thick] (5,3) -- (7,3);
  \node[acc, font=\footnotesize] at (2.2,3.55) {water level = min(L, R)};
  % annotate one trapped column
  \node[font=\footnotesize, red!75!black, align=center] at (2.5,-0.6)
    {trapp\/ed = min($L_i$, $R_i$) - h[i]};
\end{tikzpicture}
$$

::impl{algo="trapping_rain_water"}

## Choosing the tool

The variants differ only in stack order and one comparison. To read the table:
the popped element's next-side answer is the arriving index $i$, and the pushed
element's previous-side answer is whatever the new top is, with the strictness
complemented.

| target (to the right) | stack values | pop while |
|---|---|---|
| next strictly greater | decreasing | $a[\text{top}] < a[i]$ |
| next greater or equal | decreasing | $a[\text{top}] \le a[i]$ |
| next strictly smaller | increasing | $a[\text{top}] > a[i]$ |
| next smaller or equal | increasing | $a[\text{top}] \ge a[i]$ |

For maxima over a _moving window_, trade the stack for a decreasing deque (an
increasing deque for windowed minima). The recurring mistakes:

- **Push indices, not values.** Widths ($i - L - 1$), distances ($j - i$), and
  deque expiry all need positions; the values are one array lookup away.
- **Choose strictness per side, deliberately.** For a single next-greater query
  any consistent choice works; for counting problems, symmetric choices
  double-count or miss subarrays whose extreme value appears more than once.
- **Do not forget the histogram sentinel.** Bars surviving the scan still owe
  a rectangle that reaches the right edge; a strictly increasing input pops
  nothing without the sentinel and returns $0$.
- **Expire the deque front by index arithmetic** ($\text{front} \le i - k$),
  never by comparing values, and emit window outputs only from $i = k$ on.
- **Never re-push a popped element.** The $O(n)$ bound amounts to the statement
  that each index is pushed once and popped at most once; any "put it back and
  retry" variation forfeits linearity.

## Cartesian trees, monotonic queues, and maximal rectangles

The monotonic stack is the algorithmic core of a data structure textbooks treat
separately: the **Cartesian tree** (Vuillemin, _A Unifying Look at Data
Structures_, CACM 1980). Build a Cartesian tree of an array — a binary tree that
is a min-heap by value and an in-order traversal by index — and its parent-child
links encode the "nearest smaller to the left/right" relations the
monotonic stack computes; in fact the standard $O(n)$ Cartesian-tree
construction _is_ a monotonic-stack sweep. That connection is what links this
lesson to two others: the range-minimum-query problem reduces to lowest-common-
ancestor on the Cartesian tree, and the tree's structure underlies the
**treap** (tree + heap) balanced-BST variant.

The sliding-window-maximum deque generalizes to the **monotonic queue
optimization** for dynamic programming: a DP recurrence of the form
$dp[i] = \min_{j \in [i-k,\, i-1]} (dp[j] + \text{cost}(j, i))$, where the window
of valid $j$ slides forward, is evaluated in $O(n)$ instead of $O(nk)$ by
keeping the candidates in a monotonic deque — the same expire-the-front,
pop-the-dominated logic, applied to DP values rather than array elements. This is
the standard speedup for problems like "jump game with a bounded reach" and
appears in the [DP-optimizations](/algorithms/dynamic-programming/dp-optimizations)
material as the deque case of the more general convex-hull and Knuth
optimizations.

The largest-rectangle-in-a-histogram routine, finally, is the one-dimensional
kernel of the **maximal-rectangle** problem on a binary matrix: process the
matrix row by row, maintaining for each column the height of the run of ones
ending at the current row, and run the histogram scan on each row's height
array — an $O(rc)$ algorithm for an $r \times c$ matrix that would otherwise
look hopelessly combinatorial.

## 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 height-$0$ **sentinel**
  flushes the final increasing run.
- 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)$.
- **Duplicates are a tie-breaking decision.** Reporting a single extreme
  tolerates either strictness; counting each subarray once requires **strict on
  one side, non-strict on the other**, as in the sum of subarray minimums and,
  implicitly, the fused histogram scan.
- **Daily temperatures**, **stock span**, and **trapping rain water** are the same
  previous/next-greater machinery pointed in different directions.

[^skiena-sq]: **Skiena**, §3.2 — Stacks and Queues: stacks and queues as the primitives behind LIFO/FIFO scans; the monotonic discipline turns them into linear nearest-greater solvers.
[^clrs-amortized]: **CLRS**, Ch. 16 — Amortized Analysis: aggregate and potential-method bounds; the stack whose elements are each pushed and popped at most once is the canonical example.
[^skiena-deque]: **Skiena**, §3.2 — Stacks and Queues: the deque (double-ended queue) supporting $O(1)$ push/pop at both ends, the structure underlying $O(n)$ sliding-window maxima.