前言 | Preface
这几天连续做了好几道单调队列的题，难度从绿到蓝不等，摸索出了一些经验，也总结了一些单调队列的特点和规律。
概述 | 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\)，换言之，这个单调队列里的元素是单调递增的。
总的来说，单调队列解决这道题（以最大值为例）的过程分为两步：
- 加入新的元素时，从队尾踢掉之前所有比它小的数，并自己加入队尾
- 从队头移除已经离开窗口的数
此时队头即为最大值。
附上我用的模板代码：
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)\) 线性的。
当 OIer 换成规则的制订者，数列元素换成一个个活生生的人，无处不在的淘汰机制就是一个巨大的单调队列。人们总是钟爱年轻而实力强的，抛弃年长而实力弱的，而这往往也带来最高的效率。
那一个被 \(y\) 所干掉的 \(x\)、被新加入的 a[i] 一路碾死的 a[q[tail]] 们总是大多数人。不想成为他们中的一员，就只能不断提升自己。数列元素的命运在输入的那一刻已经注定，而人尚能不断提升，为生命争取不被淘汰的资格。
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} \]
\(\max_{p=j-t}^{j+t} f_{i-1,p}\)，标准的定长区间最值问题，这一部分用单调队列来计算，即可优化成 \(O(nm)\)。
P2216 [HAOI2007] 理想的正方形
正方形大小 \(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
转化一下，将“不能连续选择超过 \(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 选择数字
跟上面那道题一样，不再赘述。
P1419 寻找段落
推荐题解：点击这里，不过单调队列部分不太详细。
最终是要判定是否存在 \(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 普及组] 跳房子 \(\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}\)
综上所述，单调队列代码简短而好写，能够解决的问题范围清晰，是一种很实用的数据结构。单调队列不常作为一个裸的知识点来单独考，而是常常与动态规划等问题结合在一起，用作优化时间复杂度。
单调队列可以优化的问题具有以下特点：
- 在一个区间 \([l,r]\) 上求最值；
- 区间左右端点 \(l,r\) 均单调不减/单调不增。
同时，类似滑动窗口这种 “（连续移动的）定长区间最值问题”是单调队列中考得最多的一种，也是必须掌握的一种。
下面附上一份更加通用的单调队列模板（或者说其实算是伪代码？）：
定义/清空单调队列 //需要队头队尾均可压入和弹出，如双端队列
for(int i=1;i<=n;i++)
{
while(队列非空 && 队头超出范围) 弹出队头;
while(队列非空 && 队尾劣于当前元素i) 弹出队尾;
队尾压入i;
//此时队头为最优元素，按题目需要使用
}