◄ WORLD V · SONNY 5DART 314 · a helldive at the net

THE MONOTONIC QUEUE a deque that evicts the dominated — each element enters and leaves once

To find the maximum in every sliding window, the naive way rescans each window: O(nk), re-reading values again and again. The monotonic queue refuses to re-read. It keeps a double-ended queue of candidates in decreasing order; when a new value arrives it evicts from the back every element it dominates (they can never again be a maximum — the newcomer is bigger and younger), then it appends. The front is always the window's maximum. The eviction is the trick: each element is pushed once and popped once, so the whole sweep is O(n), with a deque bounded by the window. Dominated candidates are thrown away and never revisited — that discarding is the mechanism.

THE TECHNIQUE decreasing deque; evict dominated at the back, front = window max

A stream and a window of 3. The demo maintains the monotonic deque and reports each window's maximum, showing the evictions: live demo







  
HISTORY & CREDIT the sliding-window-minimum deque · algorithmic folklore

  
“Window maxima cost O(nk).” — the monotonic deque makes it O(n): each value is admitted once and evicted once, and a dominated candidate is discarded forever the moment a bigger, younger one appears. cited

  
folklore · the “ascending-minima” / monotonic-deque technique for sliding-window extrema, long circulated in competitive programming and streaming.
generalization · the same idea underlies the van Herk / Gil–Werman (1992–93) O(1)-per-pixel morphological max-filter.
now · sliding-window max/min, the constraint in many DP speedups, real-time envelope followers.

  
A queue that only ever holds those still in the running; the rest are cast out and never seen again. Linear work from ruthless forgetting. monotonic deque






  
RECOMMEND FOR I-13 the sliding-window maximum, on the compiler

  
On the canonical compiler, the maximum of the last window of [1,3,−1,−3,5,3] is 5 — the dominated candidates having been evicted:

  
$ i13 run op_monoqueue.i13   # front of the monotonic deque = window max
RUN OK · 103 step(s) · peak stack 7 · call depth 4
window_max = 5      -- dominated candidates evicted, never revisited

  
Recommend: the monotonic queue is the theme's most muscular mechanism — the eviction of the dominated is a real act, not bookkeeping: a correct rescan re-reads every window (O(nk)); the deque admits and evicts each element once (O(n)) and throws dominated candidates away for good. That discarding is the supplement to correctness a rescan lacks. It falls short of a keeper on two honest counts, surfaced to the panel: (1) i13 here computes the window max by the bounded sweep, but does not build the deque structure itself, so the eviction is described, not fully enacted on the compiler; (2) the property it supplies (linear vs quadratic work) is an efficiency property, and the B39 bar asks for a structural property a correct alternative cannot have, not merely one it is slower without. Kept as the sharpest near-miss of the batch.