单调队列(Monotonic Queue)

17 Aug 2025

1.简介

单调队列与单调栈相似。应先学习单调栈，再学习单调队列。
单调队列保持单调的特性，可以单调递增，也可以单调递减。
单调队列在动态规划中用于优化状态转移，或处理数据流中的实时最值问题。

2.实现

对于长度为n的序列，有一个长度为k的窗口。窗口从左到右，每次滑动一个单位。求每次滑动后窗口内的最大值和最小值。

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

思路：

用一个双端队列deque来模拟窗口。因为窗口在滑动的过程中，一端进，一端出，所以选择队列。另外，队尾既需要push也需要pop，所以使用双端队列。
与单调栈相同，单调队列存入的是元素的下标。
首先考虑窗口如何滑动。窗口移动之后，在开始求最值前，要先把已经移动到窗口之外的数字从队列中去掉。我们从队尾加入元素，从队头踢出元素。若i表示当前的元素，那么当q.front() < i - k + 1时，说明a.front()已经在窗口之外，应该踢出。
窗口滑动完之后，可以开始求最值。求最大值时，若队尾比当前元素小，则踢出。踢出之后，得到新的队尾，继续与当前元素比较，知道队列为空，或队尾大于等于当前元素。求最小值类似。这样是求最值的优化，和单调栈相同，没有必要把整个窗口遍历一遍。
比如，在求最大值的时候，我们维护一个从队头到队尾单调递减的队列，那么队头始终是当前元素的答案。

在样例中，当枚举到元素5时，队列为 [3, -1, -3] (左边为front，右边为back。队列存的是元素而不是下标，方便理解)。

此时判断3已经在窗口之外，所以踢出。

对于-1和-3，它们都比当前元素5小。由于5的存在，-1和-3对于后面的元素，不可能成为它们的答案，所以踢出。

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.变形

example 1: 洛谷P1714 求最大字段和 (给定了子段的长度为m)

题意： \(在\ p_n中，找出一个子段 [l,r]\ (r−l+1≤m)，最大化 ∑_{i=l}^{r} \ p_i\) 与模版不同之处在于，此题需要求和，而非找到最值。因此需要使用前缀和。

用前缀和将序列处理完成之后，得到一个sum[]的数组，因此求[l,r]区间的和，可以用sum[r]-sum[l-1]来表示。

思路：

对于sum[i]，把它看作区间的右端点。遍历sum数组时，每一轮循环中i的值是确定的，那么右端点也是确定的，所以目标转移到了求左端点。
区间和表示为sum[r] - sum[l-1]，由于sum[r]是确定的，因此当sum[l-1]最小时，区间和最大。
所以可以在每一轮循环中，用单调队列找到sum[l-1]的最小值。求sum[l-1]的最小值，已经和单调队列模版没有区别。相当于是一个长度为n的序列 (sum数组)，窗口长度为m，找到每个窗口的最小值。

example 2: 洛谷P2216 (二维)

题意：

有一个 a×b 的整数组成的矩阵，现请你从中找出一个 n×n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

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

output
1

思路：

这道题也是求区间内的最值，只不过是二维的，那么可以试着将二维转化为一维。
令 c [i] [j]表示在 (i, j) 所在的竖列中，以 (i, j)为起点，向上的一个长度为n的序列的最大值。如 c[5] [2] = 10，因为它所在的数列为 [2, 10]。
那么，max(c[i] [j], c[i] [j+1], c[i] [j+2] …….. c[i] [j + n -1]) 就是一个以 (i, j)为左下方顶点的 n×n 矩形中的最大值。求最小值的方法一样，用d[i] [j]表示。
用单调队列求数组c和数组d，和求滑动窗口中的最值无异。
处理完数组c和数组d之后，再枚举所有的矩形即可。

单调队列(Monotonic Queue)

Related Posts