单调队列 Notes
Mars_Dingdang
2020-12-26 16:23:32
### 一、引入
1.1 定长滑窗问题：
给出一列 $n$ 个正整数，和一个固定长度为 $k$ 的滑动窗口, 从左到右在数列中滑动这个窗口，找到数列中每个窗口内的最大值。
即对于给定数列 $A_1\sim A_n$ $(1\le n\le 10^7)$，求每一个 $f_i=\min\limits_{j=i-k+1}^{i}A_j$。
### 二、数据维护
#### 2.0 线段树，RMQ
这两者与 2.1 都是 $\Theta(n\log n)$ 级别的复杂度，且代码量较大，因此略过。
#### 2.1 多重集
2.1.1 简介
multiset 是 STL 容器中的一种，中文名为多重集。多重集是按照特定顺序存储元素的容器，其中多个元素可以具有相等的值。
其底层数据结构为红黑树，是一种高度平衡的二叉搜索树，因此插入，搜索和删除都是 $\Theta (\log n)$ 的复杂度，而对于根节点的访问则是 $\Theta(1)$ 的。
2.1.2 解决方法
每一次插入新的元素，并删除旧元素。由于 multiset 自动按从小到大进行排序，因此一段定长区间的最大值即为 `*s.rbegin()`。
2.1.3 代码
```cpp
multiset<int,greater<int> > s; //从大到小排序，不去重
inline void Multiset(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);//input
for(int i=1;i<=n;i++){
s.insert(x[i]);//插入
if(s.size()>k) s.erase(s.find(x[i-k]));//删除元素维持定长
ans[i]=*s.begin();//记录最值
}
for(int i=k;i<=n;i++) printf("%d ",ans[i]);
}
```
#### 2.2 单调队列
2.2.1 简介
这时候大家一定会想：有没有更有的算法复杂度（比如线性）呢？答案是肯定的。这时候就需要单调队列发挥作用了。
单调队列，即单调递减或单调递增的队列，是一种特殊的双端队列 (deque)，有以下两种操作：
1. 插入：将新元素从队尾插入，若破坏单调性则重复删除队尾元素再插入。
2. 查询最值：访问队首元素。
为了方便起见，队列中存储元素在原数列的下标（编号），利于维持定长。
2.2.2 操作
$q[i]$ 表示单调队列 i 号元素在原 x 数组的编号
$ans[i]$ 表示以 i 结尾的窗口里的最值
- 发现 $i-q[l] >= k$ 则 `l++` $|\ l<r$ //左删维持定长
- 发现 $x[i]>=x\left[q[r-1]\right]$ 则 `r--` $|\ l<r$ //右删维持单调性
- 将元素插入 `q[r++] = i`。
很明显，由于每个元素最多出队一次，进队一次，因此时间复杂度是 $\Theta(n)$。
2.2.3 正确性及性质
对于相邻两个区间 $(L,R)$ 以及 $(L+1,R+1)$ 有以下性质：
对于序列 $A_1,A_2\cdots A_n$，区间 $(L,R)$ 中
$\min\{A_L\sim A_R\}=\min\left\{A_L,\min\{A_{L+1}\sim A_R\}\right\}$，
$\min\{A_{L+1}\sim A_{R+1}\}=\min\left\{A_{R+1},\min\{A_{L+1}\sim A_R\}\right\}$。
两个方程有相同的部分 $\min\{A_{L+1}\sim A_R\}$，因此其最值落在 $(L+1,R)$ 的概率极大，那么在求 $(L+1,R+1)$ 的最值时没有必要重新扫描一遍，只有当最值为 $A_l$ 才需重新扫描。这样，算法得到了极大的优化。
同时，对于任意的 $[i,j]\in [L,R]$，若 $A_i<A_j$，在区间右移时，最值永远也不会落在 $A_i$ 上，因此 $A_i$ 比 $A_j$ 先失效。这个性质与单调队列性质相符。
2.2.4 代码
例题：[滑动窗口](https://www.luogu.com.cn/problem/P1886)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,k,x[maxn],ans[maxn];
deque<int> q; //双端队列
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++){
while(!q.empty() && i-q.front()>=k) q.pop_front();//左删
while(!q.empty() && x[i]<x[q.back()]) q.pop_back();//右删
q.push_back(i);//插入元素编号
ans[i]=x[q.front()];//记录最小值
}
for(int i=k;i<=n;i++) printf("%d ",ans[i]);
q.clear();
memset(ans,0,sizeof(ans));
putchar('\n');//初始化 + 换行
for(int i=1;i<=n;i++){
while(!q.empty() && i-q.front()>=k) q.pop_front();//左删
while(!q.empty() && x[i]>x[q.back()]) q.pop_back();//右删
q.push_back(i);//插入元素编号
ans[i]=x[q.front()];//记录最大值
}
for(int i=k;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
```