单调队列:实用而好写的数据结构
前言 | Preface
这几天连续做了好几道单调队列的题,难度从绿到蓝不等,摸索出了一些经验,也总结了一些单调队列的特点和规律。
本文作者:Jerrycyx
本文在以下平台同步发送:洛谷、博客园、CSDN
推荐在洛谷专栏阅读以获得更好的阅读体验。
概述 | Outline
顾名思义,单调队列的重点分为「单调」和「队列」。
「单调」指的是元素的「规律」——递增(或递减)。
「队列」指的是元素只能从队头和队尾进行操作。
——OI Wiki
单调队列(monitonous queue) 是一种很实用的数据结构。如何理解单调队列?首先,“队列”其实是指双端队列,因为单调队列队首队尾都可以进出;其次“单调”是指单调队列里的元素具有单调性(单调递增或递减均可)。
我知道你没看懂。 单调队列光靠这些文字叙述确实不好理解,结合例题就能明白了。
(大佬不想看例题可直接跳转至「总结 | Summary」部分)
例题 | Example
本文重点为单调队列,所以其他算法内容一律从略,且一般会有引用的格式加以标明。
下面有一半的绿题都是我从蓝降下来的。
P1886 滑动窗口 /【模板】单调队列 \tt\textcolor{Orange}{\bigstar Important}
老生常谈的单调队列模板题了,但是我之前每次都不会做,题面说得很清楚,下面来说单调队列的运作方式。
单调队列的核心思想就是:“老而更劣的元素永远不可能成为最值”(让我想起了我的 OI 生涯)。
例如,在求最大值时有两个元素
现实是残酷的,OIer 们是残忍的,
如此,单调队列保证了其中不存在
总的来说,单调队列解决这道题(以最大值为例)的过程分为两步:
- 加入新的元素时,从队尾踢掉之前所有比它小的数,并自己加入队尾
- 从队头移除已经离开窗口的数
此时队头即为最大值。
附上我用的模板代码:
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];
}
每个元素最多入队出队一次,所以时间复杂度是
P1725 琪露诺
呵呵,这道题我其实打了个线段树。
单调队列优化动态规划题。
设
f_i 表示走到位置i 所获得的最大冰冻指数,那么有:f_i = a_i + \max_{j=i-R}^{i-L}f_j
暴力求
这道题会有一些细节处理问题,不过不是重点。
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}
我的题解:点击这里
显然,使
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 ),这样加入后无法立即弹出,非法的答案就进入到队列当中了。这也解答了这个帖子中提出的问题。
上面几道例题,可能让大家认为“定长区间最值问题”都可以用单调队列维护。然而,这只是单调队列的一种比较经典的用法,且必须要求区间连续移动。
实际上,如上面引用的题解内容所说:“在一个
比如上面那道题,区间长度可能随时变化,有时甚至会缩成空集,但是只要它左右端点单调不减,就可以用单调队列求最值。
P2254 [NOI2005] 瑰丽华尔兹
最后放一道单调队列模板练习题,相信手打并调完这道题,你会对单调队列的各种细节和不同的打法倒背如流的 XD。
推荐题解:点击这里
总结 | Summary \tt\textcolor{Orange}{\bigstar Important}
综上所述,单调队列代码简短而好写,能够解决的问题范围清晰,是一种很实用的数据结构。单调队列不常作为一个裸的知识点来单独考,而是常常与动态规划等问题结合在一起,用作优化时间复杂度。
单调队列可以优化的问题具有以下特点:
- 在一个区间
[l,r] 上求最值; - 区间左右端点
l,r 均单调不减/单调不增。
同时,类似滑动窗口这种 “(连续移动的)定长区间最值问题”是单调队列中考得最多的一种,也是必须掌握的一种。
下面附上一份更加通用的单调队列模板(或者说其实算是伪代码?):
定义/清空单调队列 //需要队头队尾均可压入和弹出,如双端队列
for(int i=1;i<=n;i++)
{
while(队列非空 && 队头超出范围) 弹出队头;
while(队列非空 && 队尾劣于当前元素i) 弹出队尾;
队尾压入i;
//此时队头为最优元素,按题目需要使用
}
当 OIer 换成规则的制订者,数列元素换成一个个活生生的人,无处不在的淘汰机制就是一个巨大的单调队列。人们总是钟爱年轻而实力强的,抛弃年长而实力弱的,而这往往也带来最高的效率。
那一个被 a[i]
一路碾死的 a[q[tail]]
们总是大多数人。不想成为他们中的一员,就只能不断提升自己。数列元素的命运在输入的那一刻已经注定,而人尚能不断提升,为生命争取不被淘汰的资格。
创作不易,如果对您有所帮助,还请点赞支持,谢谢!QwQ
本文采用「CC-BY-NC 4.0」创作共享协议,转载请注明作者及出处,禁止商业使用。