Monotonic Queue

17 Aug 2025

1. Introduction

A monotonic queue is similar to a monotonic stack; it is helpful to learn the stack first.
It maintains monotonic order, either increasing or decreasing.
It is used to optimize dynamic-programming transitions and to maintain sliding-window extrema in a data stream.

2. Implementation

For a sequence of length n, a window of length k moves from left to right one position at a time. Find the maximum and minimum in the window after every move.

input
8  3
1  3  -1  -3  5  3  6  7

output
min -1 -3 -3 -3  3  3
max  3  3  5  5  6  7

Approach:

Use a deque to simulate the window. One end enters while the other leaves as the window moves, and the back needs both push and pop operations.
As with a monotonic stack, store element indices rather than values.
Before finding an extremum after moving the window, remove indices that have left the window. Add elements at the back and remove expired ones from the front. For current index i, q.front() < i - k + 1 means that the front lies outside the window and must be removed.
For a maximum, remove elements from the back while they are smaller than the current element. Continue until the queue is empty or the value at its back is at least the current value. Minima are analogous. This avoids traversing the entire window.
For a maximum, maintain a queue decreasing from front to back, so the front is always the answer. Although the implementation stores indices, the corresponding values in the sample are [3, -1, -3] from front to back before 5 is processed. Remove 3 because its index has expired; remove -1 and -3 because 5 is greater and they can never be answers for later elements.

for(int i = 1; i <= n; i++) { // 求最大值
		while(!q.empty() && q.front() < i - k + 1)
			q.pop_front();
		while(!q.empty() && a[q.back()] < a[i])
			q.pop_back();
		q.push_back(i);
  	maxi[i] = a[q.front()];
}

for(int i = 1; i <= n; i++) { // 求最小值
		while(!q.empty() && q.front() < i - k + 1)
			q.pop_front();
		while(!q.empty() && a[q.back()] > a[i])
			q.pop_back();
		q.push_back(i);
		mini[i] = a[q.front()];
}

3. Variations

Example 1: Luogu P1714, maximum subarray sum with a length limit m.

Task: Given a sequence p₁, …, p_n, find a subarray [l, r] with r − l + 1 ≤ m that maximizes Σ_{i = l}^r p_i. Unlike the template, this problem asks for a sum rather than an extremum, so use prefix sums.

After preprocessing prefix sums in sum[], the sum on [l,r] is sum[r]-sum[l-1].

Approach:

Treat sum[i] as the right endpoint. During each iteration i is fixed, so the task becomes choosing the left endpoint.
Since the interval sum is sum[r] - sum[l-1] and sum[r] is fixed, the sum is maximal when sum[l-1] is minimal.
Use a monotonic queue to find the minimum valid sum[l-1] in each iteration. This is exactly a sliding-window minimum over the sum array with window length m.

Example 2: Luogu P2216 (two-dimensional).

Task:

Given an a×b integer matrix, find an n×n square in which the difference between the maximum and minimum values is minimal.

input
a = 5, b = 4, n = 2
 2   5   6
 17  16  0
17  2   1
 10  2   1
 2   2   2

output
1

Approach:

This is also a range-extrema problem, but in two dimensions, so reduce it to one-dimensional steps.
Let c[i][j] be the maximum in the length-n vertical sequence starting at (i,j) and extending upward. For example, c[5][2] = 10 because that sequence is [2, 10].
Then max(c[i][j], c[i][j+1], …, c[i][j+n-1]) is the maximum of the n×n square whose lower-left corner is (i,j). Compute minima similarly with d[i][j].
Compute c and d with monotonic queues just as for one-dimensional sliding-window extrema.
Finally enumerate all squares.

Monotonic Queue

Related Posts