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 $Θ (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 $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 $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 $\geq 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:

\textsc{Next-Greater}(a[1..n])

— next strictly-greater element to the right

1
$S \gets$ empty stack of indices
2
for $i \gets 1$ to $n$ do
3
while $S$ not empty and $a[\text{top}(S)] < a[i]$ do
4
$j \gets \text{pop}(S)$
5
$\text{nge}[j] \gets i$
$a[i]$ : $j$ 's next-greater
6
$\text{push}(S, i)$
unresolved
7
while $S$ not empty do
8
$\text{nge}[\text{pop}(S)] \gets \text{none}$
no greater right

The scan, push by push

Here is the complete run on $a = ⟨ 2, 5, 3, 1, 4 ⟩$ . 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$ : $nge [1] = 2$	$2 (5)$
$3$	$3$	—	$2 (5), 3 (3)$
$4$	$1$	—	$2 (5), 3 (3), 4 (1)$
$5$	$4$	pop $4$ : $nge [4] = 5$ ; then pop $3$ : $nge [3] = 5$	$2 (5), 5 (4)$
end	—	pop $5$ , then $2$ : $nge = none$	$\emptyset$

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 \geq 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 $none$ : nothing to their right ever beat them.

Next-greater scan on

a = ⟨ 2, 5, 3, 1, 4 ⟩

at the decisive step. Arriving

a [5] = 4

pops indices

4

then

3

(values

1, 3

both

< 4

), assigning

nge [4] = nge [3] = 5

; index

2

(value

5 \geq 4

) survives, then

5

is pushed

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

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

The same bound falls out of the potential method with $Φ =$ stack size: an iteration that pops $k$ elements costs $k + O (1)$ real work but decreases the potential by $k - 1$ , so its amortized 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$ .²

Strictness, and the four cousins

The pop condition $a [top] < a [i]$ is strict, so equal values do not resolve each other: on $a = ⟨ 3, 3, 5 ⟩$ 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 [top] \leq a [i]$ instead. One comparison character changes which of the two $3$ s answers for which subarrays, and the section on counting subarray minimums shows why that choice is sometimes forced.

Flipping the comparison to $a [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- $\leq$ 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 $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, \dots, 2 n$ , comparing against $a [((i - 1) mod n) + 1]$ but pushing only while $i \leq n$ : the first pass builds the stack, the second lap only resolves the leftovers that needed to wrap around.

next_greater_element.pypython

from typing import Optional, Sequence, TypeVar

from comparable import Comparable

Value = TypeVar("Value", bound=Comparable)

def next_greater_element(values: Sequence[Value]) -> list[Optional[int]]:
  """
    For each index, the smallest index to its right with a strictly greater\n
    value, or None when no such index exists.\n
  """
  answer: list[Optional[int]] = [None for _ in range(len(values))]

  # indices whose next-greater is still unknown, values strictly decreasing
  # from bottom to top of the stack.
  unresolved: list[int] = []
  for index in range(len(values)):

    # every shorter pending index has just found its next-greater.
    while unresolved and values[unresolved[-1]] < values[index]:
      resolved: int = unresolved.pop()
      answer[resolved] = index
    unresolved.append(index)
  return answer

def next_smaller_element(values: Sequence[Value]) -> list[Optional[int]]:
  """
    For each index, the smallest index to its right with a strictly smaller\n
    value, or None when none exists. The next-greater scan with the\n
    comparison flipped and an increasing stack.\n
  """
  answer: list[Optional[int]] = [None for _ in range(len(values))]

  # taller pending indices have just found their next-smaller.
  unresolved: list[int] = []
  for index in range(len(values)):
    while unresolved and values[unresolved[-1]] > values[index]:
      resolved: int = unresolved.pop()
      answer[resolved] = index
    unresolved.append(index)
  return answer

def previous_greater_element(values: Sequence[Value]) -> list[Optional[int]]:
  """
    For each index, the largest index to its left with a strictly greater\n
    value, or None when none exists. The next-greater scan run right to left.\n
  """
  answer: list[Optional[int]] = [None for _ in range(len(values))]

  # scan right-to-left so "previous" becomes "next" on the reversed sweep.
  unresolved: list[int] = []
  for index in range(len(values) - 1, -1, -1):
    while unresolved and values[unresolved[-1]] < values[index]:
      resolved: int = unresolved.pop()
      answer[resolved] = index
    unresolved.append(index)
  return answer

def previous_smaller_element(values: Sequence[Value]) -> list[Optional[int]]:
  """
    For each index, the largest index to its left with a strictly smaller\n
    value, or None when none exists.\n
  """
  answer: list[Optional[int]] = [None for _ in range(len(values))]

  # right-to-left with a flipped comparison for the strictly-smaller side.
  unresolved: list[int] = []
  for index in range(len(values) - 1, -1, -1):
    while unresolved and values[unresolved[-1]] > values[index]:
      resolved: int = unresolved.pop()
      answer[resolved] = index
    unresolved.append(index)
  return answer

daily_temperatures.pypython

from typing import Sequence

def daily_temperatures(temperatures: Sequence[int]) -> list[int]:
  """
    For each day, how many days you must wait for a strictly warmer\n
    temperature; 0 if no warmer day follows.\n
  """
  waits: list[int] = [0 for _ in range(len(temperatures))]

  # indices of days still waiting for a warmer day; their temperatures are
  # strictly decreasing from bottom to top of the stack.
  unresolved: list[int] = []
  for today in range(len(temperatures)):

    # today resolves every colder day still waiting on the stack.
    while unresolved and temperatures[unresolved[-1]] < temperatures[today]:
      earlier_day: int = unresolved.pop()
      waits[earlier_day] = today - earlier_day
    unresolved.append(today)
  return waits

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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:

area = h [t] \cdot (i - (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]$ .

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

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:

\textsc{Largest-Rectangle}(h[1..n])

— fused previous/next-smaller scan

1
$S \gets$ empty stack of indices; append sentinel $h[n+1] \gets 0$
2
$\text{best} \gets 0$
3
for $i \gets 1$ to $n+1$ do
4
while $S$ not empty and $h[\text{top}(S)] \ge h[i]$ do
5
$t \gets \text{pop}(S)$
6
$L \gets$ ( $S$ empty $?$ $0$ $:$ $\text{top}(S)$ )
previous-smaller bar
7
$\text{best} \gets \max(\text{best},\; h[t] \cdot (i - L - 1))$
8
$\text{push}(S, i)$
9
return $\text{best}$

The whole computation, worked

Take $h = ⟨ 3, 2, 4, 5, 1 ⟩$ , 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$ .

The pop sequence at trigger

i = 5

h = ⟨ 3, 2, 4, 5, 1 ⟩

: 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

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 $Θ (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 [top] \geq h [i]$ (non-strict), so an arriving bar pops earlier bars of the same height. On $h = ⟨ 2, 2 ⟩$ 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.

largest_rectangle_histogram.pypython

from typing import Sequence

def largest_rectangle_histogram(heights: Sequence[int]) -> int:
  """
    Area of the largest rectangle that fits under the bars of unit width.\n
    Heights are non-negative. An empty histogram has area 0.\n
  """
  best: int = 0

  # bar indices whose right limit is still unknown; their heights are
  # increasing from bottom to top of the stack.
  unresolved: list[int] = []
  bar_count: int = len(heights)
  for position in range(bar_count + 1):

    # a sentinel height of 0 past the end flushes everything still stacked.
    current_height: int = 0 if position == bar_count else heights[position]

    # each popped bar is bounded right by `position`, left by the new top.
    while unresolved and heights[unresolved[-1]] >= current_height:
      tallest: int = unresolved.pop()
      left_limit: int = unresolved[-1] if unresolved else -1
      width: int = position - left_limit - 1
      best = max(best, heights[tallest] * width)
    unresolved.append(position)
  return best

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

Push back, popping smaller tails. While the back's value is $\leq 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.
Expire the front. If the front index has fallen out of the window ( $front \leq i - k$ ), pop it from the front.

Sliding-window maximum with a decreasing deque; window

[l, r]

over

a

, deque front (in accent) is the window max

A full stream

The run on $a = ⟨ 1, 3, 5, 2, 4, 6 ⟩$ 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.³

sliding_window_maximum.pypython

from collections import deque
from typing import Sequence, TypeVar

from comparable import Comparable

Value = TypeVar("Value", bound=Comparable)

def sliding_window_maximum(
  values: Sequence[Value], window: int
) -> list[Value]:
  """
    The maximum of each contiguous window of width `window`, in order of\n
    window start. Requires 1 <= window <= len(values); the result has\n
    len(values) - window + 1 entries.\n
  """
  if window <= 0:
    raise ValueError("window width must be positive")
  if window > len(values):
    raise ValueError("window width exceeds the sequence length")

  maxima: list[Value] = []

  # indices of live candidates, values strictly decreasing front to back.
  candidates: deque[int] = deque()
  for index in range(len(values)):

    # rule 1: drop tail candidates that this value out-lives and out-values.
    while candidates and values[candidates[-1]] <= values[index]:
      candidates.pop()
    candidates.append(index)

    # rule 2: expire the front once it falls out of the window.
    if candidates[0] <= index - window:
      candidates.popleft()

    # once the first full window is in view, the front is its maximum.
    if index >= window - 1:
      maxima.append(values[candidates[0]])
  return maxima

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Deque step at

i = 6

(

a [6] = 6

) on

a = ⟨ 1, 3, 5, 2, 4, 6 ⟩

. The incoming

6

exceeds both tails, so back-popping clears indices

5, 3

(values

4, 5

); the deque collapses to

⟨ 6 ⟩

, the new window-

[4, 6]

maximum

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 = ⟨ 6, 4, 3, 2, 5, 1 ⟩$ 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 \leq 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.

Deque states on

a = ⟨ 6, 4, 3, 2, 5, 1 ⟩

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

Ties again hide a decision. Rule 1 pops while the back is $\leq 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: $\leq$ 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 $(2 n + 1)$ subarrays. Summing subarray by subarray is $Θ (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} = left choices (i - P (i)) \cdot right choices (N (i) - i),

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 = ⟨ 3, 1, 2, 4 ⟩$ :

$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 = ⟨ 1, 1 ⟩$ , 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.

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.

Trapping rain water: above each bar the water rises to

min (leftMax, rightMax)

, so the trapped height at index

i

min (L_{i}, R_{i}) - h [i]

— bounded on each side by a previous/next taller bar

trapping_rain_water.pypython

from typing import Sequence

def trapping_rain_water(heights: Sequence[int]) -> int:
  """
    Total units of water trapped between the bars after rain. Heights are\n
    non-negative; fewer than three bars trap nothing.\n
  """
  left: int = 0
  right: int = len(heights) - 1
  left_max: int = 0
  right_max: int = 0
  trapped: int = 0

  # advance the lower side inward: that side's bound is settled, because the
  # opposite max is already known to be at least as tall.
  while left < right:
    if heights[left] < heights[right]:
      left_max = max(left_max, heights[left])
      trapped += left_max - heights[left]
      left += 1
    else:
      right_max = max(right_max, heights[right])
      trapped += right_max - heights[right]
      right -= 1
  return trapped

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 [top] < a [i]$
next greater or equal	decreasing	$a [top] \leq a [i]$
next strictly smaller	increasing	$a [top] > a [i]$
next smaller or equal	increasing	$a [top] \geq 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 ( $front \leq 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 $d p [i] = min_{j \in [i - k, i - 1]} (d p [j] + 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 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 (r c)$ 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, §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, 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, §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. ↩

The monotonic stack: next greater element

The scan, push by push

Strictness, and the four cousins

Largest rectangle in a histogram

The whole computation, worked

The monotonic deque: sliding-window maximum

A full stream

When the front ages out

Counting with spans: sum of subarray minimums

Why one idea covers so many problems

Choosing the tool

Cartesian trees, monotonic queues, and maximal rectangles

Takeaways

Footnotes