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

· · 算法·理论

前言 | Preface

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

本文作者:Jerrycyx

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

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

概述 | Outline

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

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

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

——OI Wiki

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

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

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

例题 | Example

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

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

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

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

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

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

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

如此,单调队列保证了其中不存在 a_i,a_j 使 i<ja_i \le a_j,即对于任意 a_i,a_j 都有 i<ja_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+gj(可能不止一个);然后弹出 a_j < a_i-d-gj,最后队首元素即为所求的 \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」创作共享协议,转载请注明作者及出处,禁止商业使用。