单调队列：实用而好写的数据结构

· · 算法·理论

前言 | Preface

这几天连续做了好几道单调队列的题，难度从绿到蓝不等，摸索出了一些经验，也总结了一些单调队列的特点和规律。

本文作者：Jerrycyx

本文在以下平台同步发送：洛谷、博客园、CSDN

推荐在洛谷专栏阅读以获得更好的阅读体验。

概述 | Outline

顾名思义，单调队列的重点分为「单调」和「队列」。

「单调」指的是元素的「规律」——递增（或递减）。

「队列」指的是元素只能从队头和队尾进行操作。

——OI Wiki

单调队列（monitonous queue） 是一种很实用的数据结构。如何理解单调队列？首先，“队列”其实是指双端队列，因为单调队列队首队尾都可以进出；其次“单调”是指单调队列里的元素具有单调性（单调递增或递减均可）。

我知道你没看懂。 单调队列光靠这些文字叙述确实不好理解，结合例题就能明白了。

（大佬不想看例题可直接跳转至「总结 | Summary」部分）

例题 | Example

本文重点为单调队列，所以其他算法内容一律从略，且一般会有引用的格式加以标明。

下面有一半的绿题都是我从蓝降下来的。

P1886 滑动窗口 /【模板】单调队列 \tt\textcolor{Orange}{\bigstar Important}

老生常谈的单调队列模板题了，但是我之前每次都不会做，题面说得很清楚，下面来说单调队列的运作方式。

单调队列的核心思想就是：“老而更劣的元素永远不可能成为最值”（让我想起了我的 OI 生涯）。

例如，在求最大值时有两个元素 x \le y，其中 x 比 y 先加入窗口，那么 y 离开窗口一定比 x 要晚。在 x 剩下的生命里，y 永远比它大，x 再也不可能成为（唯一的）最大值了。

现实是残酷的，OIer 们是残忍的，x 已经失去了成为（唯一）最大值的机会，OIer 们毫不留情地抛弃掉它，来保证留下的都是有机会成为最大值的。

如此，单调队列保证了其中不存在 a_i,a_j 使 i<j 且 a_i \le a_j，即对于任意 a_i,a_j 都有 i<j 且 a_i<a_j，换言之，这个单调队列里的元素是单调递增的。

总的来说，单调队列解决这道题（以最大值为例）的过程分为两步：

  1. 加入新的元素时，从队尾踢掉之前所有比它小的数，并自己加入队尾
  2. 从队头移除已经离开窗口的数

此时队头即为最大值。

附上我用的模板代码：

int q[N],head,tail;
...
head=1,tail=0;
for(int i=1;i<=n;i++)
{
  while(head<=tail && i-q[head]+1>k) q[head++]=0;
  while(head<=tail && a[q[tail]]>a[i]) q[tail--]=0;
  q[++tail]=i;
  if(i>=k) res[i-k+1]=q[head];
}

每个元素最多入队出队一次，所以时间复杂度是 O(n) 线性的。

P1725 琪露诺

呵呵，这道题我其实打了个线段树。

单调队列优化动态规划题。

设 f_i 表示走到位置 i 所获得的最大冰冻指数，那么有：

f_i = a_i + \max_{j=i-R}^{i-L}f_j

暴力求 \max_{j=i-R}^{i-L}f_j 时间复杂度 O(n^2)，会 TLE。但这是在一个定长数组上求最值，几乎是一个裸的单调队列模板，所以只需要对 \max_{j=i-R}^{i-L}f_j 用单调队列计算来优化就可以做到 O(n) 了。

这道题会有一些细节处理问题，不过不是重点。

P3800 Power收集

这道题我打了个 ST 表，甚至还写了题解，链接就不放了，不是重点。

引用一下我的题解：

设 f_{i,j} 表示走到坐标 (i,j) 的最大 POWER 值，那么有：

f_{i,j} = a_{i,j} + \max_{p=j-t}^{j+t} f_{i-1,p}
### [P2216 \[HAOI2007\] 理想的正方形](https://www.luogu.com.cn/problem/P2216) 正方形大小 $n$ 已经确定了，这又是一个定长区间最值问题。 不过这里区间是二维的，我们设 $f_{\max}(x,y)$ 表示以 $(x,y)$ 为右下角，边长为 $n$ 的正方形区域内元素的最大值，那么有（以下以 $a$ 代表矩阵数组）： $$f_{\max}(x,y) = \max_{i=x-n+1}^{x} \max_{j=y-n+1}^{y} a_{i,j} = \max_{i=x-n+1}^{x} \left( \max_{j=y-n+1}^{y} a_{i,j} \right)$$ 我们先在 $a$ 上对每一行跑一遍单调队列求出 $f'_{\max}(x,y) = \max_{j=y-n+1}^{y} a_{i,j}$，再在 $f'_{\max}$ 上对每一列跑一遍单调队列求出 $f_{\max}(x,y) = \max_{i=x-n+1}^{x} f'_{\max}(i,y)$。 对最小值进行同样操作后，$\max\{f_{\max}(i,j)-f_{\min}(i,j)\}$ 即为所求。 ### [P2627 [USACO11OPEN] Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627) > 转化一下，将“不能连续选择超过 $k$ 头奶牛”转化成“相邻两头不选的奶牛之间间距不超过 $k$”，然后要使选择的奶牛效率值最大，也就是使不选的奶牛效率值最小。 > > 为与“选择”区分，以下以“标记”来代表“不选择”。设 $f_i$ 表示在标记了第 $i$ 头奶牛的情况下，满足“相邻两头被标记的奶牛之间间距不超过 $k$”的条件，前 $i$ 头奶牛所获得的最小效率值，那么有： > > $$f_i = e_i + \min_{j=i-k-1}^{i-1} f_j$$ > > 最终答案为 $\sum_{i=1}^{n}e_i - f_{n+1}$（$f$ 算到效率值为 $0$ 的 $n+1$ 以保证 $1 \sim n$ 全部满足条件且没有必须标记的要求，方便最后统计答案） 直接计算时间复杂度 $O(nk)$，但是观察到上式 $\min_{j=i-k-1}^{i-1} f_j$ 部分在找 $f$ 在区间 $[i-1,i-k-1]$ 内的最小值，这又是一个**定长区间最值问题**，直接塞单调队列模板即可优化成 $O(n)$。 ### [P2034 选择数字](https://www.luogu.com.cn/problem/P2034) 跟上面那道题一样，不再赘述。 ### [P1419 寻找段落](https://www.luogu.com.cn/problem/P1419) 推荐题解：[点击这里](https://www.luogu.com.cn/article/fwzyplbw)，不过单调队列部分不太详细。 最终是要判定是否存在 $r-l+1 \in [s,t]$ 使得 $sum_r-sum_{l-1} \ge 0$。转化一下，存在 $l-1 \in [r-t,r-s]$ 使得 $sum_{l-1} \le sum_r$。即： $$\min_{l-1 \in [r-t,r-s]} sum_{l-1} \le sum_r$$ 其中 $\min_{l-1 \in [r-t,r-s]} sum_{l-1}$ 又是一个定长区间最值问题，单调队列优化后即可通过。 ### [P3957 \[NOIP2017 普及组\] 跳房子](https://www.luogu.com.cn/problem/P3957) $\tt\textcolor{Orange}{\bigstar Important}

我的题解：点击这里

显然，使 a_j \in [a_i-d-g,a_i-d+g] 成立的 j 一定是连续的，设它的范围是 [l,r]。当 i 不断增加，即 a_i 单调不减的时候，a_i-d-g,a_i-d+g 也单调不减，l,r 自然同样单调不减。

在一个 l,r 均单调不减的区间 [l,r] 上找最小值，可以用单调队列维护（参考例题：滑动窗口）。使单调队列内元素单调递减，每次 i 右移的时候，在其中加入新的 a_j \le a_i-d+g 的 j（可能不止一个）；然后弹出 a_j < a_i-d-g 的 j，最后队首元素即为所求的 \max f_j。

上面两种操作顺序不能改变，因为可能出现新加入的 j 不合法的情况（满足 a_j \le a_i-d+g 却不满足 a_j \ge a_i-d-g），这样加入后无法立即弹出，非法的答案就进入到队列当中了。这也解答了这个帖子中提出的问题。

上面几道例题，可能让大家认为“定长区间最值问题”都可以用单调队列维护。然而，这只是单调队列的一种比较经典的用法，且必须要求区间连续移动。

实际上，如上面引用的题解内容所说：“在一个 l,r 均单调不减的区间 [l,r] 上找最小值，可以用单调队列维护”。“定长区间最值问题”可以用单调队列维护的本质原因不是区间长度固定，而是寻找最值的区间左右端点均单调不减。

比如上面那道题，区间长度可能随时变化，有时甚至会缩成空集，但是只要它左右端点单调不减，就可以用单调队列求最值。

P2254 [NOI2005] 瑰丽华尔兹

最后放一道单调队列模板练习题，相信手打并调完这道题，你会对单调队列的各种细节和不同的打法倒背如流的 XD。

推荐题解：点击这里

总结 | Summary \tt\textcolor{Orange}{\bigstar Important}

综上所述，单调队列代码简短而好写，能够解决的问题范围清晰，是一种很实用的数据结构。单调队列不常作为一个裸的知识点来单独考，而是常常与动态规划等问题结合在一起，用作优化时间复杂度。

单调队列可以优化的问题具有以下特点：

同时，类似滑动窗口这种 “（连续移动的）定长区间最值问题”是单调队列中考得最多的一种，也是必须掌握的一种。

下面附上一份更加通用的单调队列模板（或者说其实算是伪代码？）：

定义/清空单调队列 //需要队头队尾均可压入和弹出，如双端队列
for(int i=1;i<=n;i++)
{
  while(队列非空 && 队头超出范围) 弹出队头;
  while(队列非空 && 队尾劣于当前元素i) 弹出队尾;
  队尾压入i;
  //此时队头为最优元素，按题目需要使用
}

当 OIer 换成规则的制订者，数列元素换成一个个活生生的人，无处不在的淘汰机制就是一个巨大的单调队列。人们总是钟爱年轻而实力强的，抛弃年长而实力弱的，而这往往也带来最高的效率。

那一个被 y 所干掉的 x、被新加入的 a[i] 一路碾死的 a[q[tail]] 们总是大多数人。不想成为他们中的一员，就只能不断提升自己。数列元素的命运在输入的那一刻已经注定，而人尚能不断提升，为生命争取不被淘汰的资格。

创作不易，如果对您有所帮助，还请点赞支持，谢谢！QwQ

本文采用「CC-BY-NC 4.0」创作共享协议，转载请注明作者及出处，禁止商业使用。