Monotonic Queue

A deque whose contents stay sorted. Gives the sliding window minimum or maximum in $O(n)$ total — one of the highest-value techniques in the toolkit.

Sliding window maximum

vector<int> slidingMax(vector<int>& a, int k) {
    deque<int> dq;                                   // indices, values decreasing
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();   // out of window
        while (!dq.empty() && a[dq.back()] <= a[i])  dq.pop_back();  // dominated
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

For the minimum, flip the back comparison to >=.

Why it is $O(n)$

Each index is pushed exactly once and popped at most once, from either end. Every while iteration performs a pop, so the total number of iterations across the whole run is at most $n$.

Why popping the back is safe

If a[j] <= a[i] with $j<i$, then $j$ can never again be the window maximum: any future window containing $j$ also contains $i$ (since $i$ is newer), and $i$ is at least as large. It is dominated permanently, so discarding it loses nothing.

Uses

Problem	How
Sliding window max/min	directly
Monotone queue DP	dp[i] = min(dp[j]) + cost over a window
Bounded knapsack in $O(nW)$	window max per residue class
Shortest subarray with sum $\ge K$ (negatives allowed)	monotonic deque on prefix sums
Maximum of every subarray of length $\ge k$	window max plus a suffix scan
Constrained sequences (“no gap larger than $k$“)	window feasibility
Mo’s algorithm with min/max	needs the minimum queue variant

Shortest subarray with sum at least K

The clean showcase, because the two-pointer approach fails with negative numbers:

long long best = INT_MAX;
deque<int> dq;                                        // indices into pref, increasing values
for (int i = 0; i <= n; i++) {
    while (!dq.empty() && pref[i] - pref[dq.front()] >= K) {
        best = min<long long>(best, i - dq.front());
        dq.pop_front();
    }
    while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
    dq.push_back(i);
}

Both pops are justified by domination: a larger prefix earlier is useless, and once a left endpoint yields a valid window it will never yield a shorter one.

Variable-width windows

The deque works whenever the window’s left end moves monotonically. If the left end can move backwards, the deque is invalid — use a segment tree ($O(\log n)$) or a sparse table (static).

Monotonic queue vs monotonic stack

	Monotonic stack	Monotonic queue
Ends used	one	both
Answers	next/previous greater/smaller	sliding window min/max
Typical setting	”for each element, find …"	"for each window, find …”
Both	$O(n)$, amortized, elements pushed once

Getting the window minimum with a stack instead

Two stacks simulate a queue, and each stack can track its own minimum in $O(1)$. That gives a minimum queue with $O(1)$ amortized push/pop and $O(1)$ minimum — more general than the deque (it supports arbitrary push/pop rather than a sliding window) and it is what Mo’s algorithm on ranges with min needs.

See also: Monotonic Stack · Minimum Stack and Queue · Monotone Queue Optimization