单调队列

单调队列是一种队列（~~废话~~） 其中队列的元素保证是**单调递增**或者是**单调递减**的 那么**队首**的元素不就是最小（或最大）的吗？ 我们结合具体的题目来看看吧： 传送门：[P1886 滑动窗口](https://www.luogu.org/problemnew/show/P1886) ### 题目描述 现在有一堆数字共N个数字（N<=10^6），以及一个大小为k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单 位，求出每次滑动后窗口中的最大值和最小值。 例如： The array is [1 3 -1 -3 5 3 6 7], and k = 3.  ### 输入格式： 输入一共有两行，第一行为n,k。 第二行为n个数(<INT_MAX). ### 输出格式： 输出共两行，第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值 ### 输入输出样例 输入样例#1： 8 3 1 3 -1 -3 5 3 6 7 输出样例#1： -1 -3 -3 -3 3 3 3 3 5 5 6 7 这里我们只讨论最大值，最小值原理一样的 ### 解法1： 如果按照常规方法，我们在求a[i] 即i~i+k-1区间内的最值 时，要把区间内的所有数都访问一遍，时间复杂度约为 $O(nk)$。有没有一个快一点的算法呢？ ### 解法2: 很明显，当我们在计算区间$[i-k+1,i]$的最大值时，是不 是区间$[i-k+1,i-1]$我们之前已经计算过了？那么我们 是不是要保存上一次的结果呢（主要是最大值）？ 这时，单调队列登场—— 单调队列主要有两个操作：**删头**和**去尾** **1.删头 ** 如果队列头的元素**离开**了我们当前操作的区间，那么这 个元素就没有任何用了，我们就要把它删掉 **2.去尾** 假设即将进入队列的元素为$X$，队列尾指针为$tail$， 这时我们要比较二者的大小： 1* $X<q[tail]$ 此时q仍然保证着递减性，故直接将$X$插入队列尾 2*$X>=q[tail]$ 此时，队列递减性被打破，此时我们做一下操作： ① 弹出队尾元素 因为当前的$q[tail]$**不但不是最大值，对于以后的情况** **也不如$X$更优**，所以要弹出 这好比当前队列尾部的元素是个能力不足的老兵，而新加入 的新兵更年轻，更能打，当然不要老兵了 ②重复执行①，直到满足$X<q[tail]$或者队列为空为止 ③将$X$插入队列 对于样例而言： ``` [1 3 -1] -3 5 3 6 7 q={1},{3},{3,-1} output:3//分别为每次操作的结果 1 [3 -1 -3] 5 3 6 7 q={3,-1,-3} output:3 1 3 [-1 -3 5] 3 6 7 q={-1,-3},{-1,5},{5} output:5 1 3 -1 [-3 5 3] 6 7 q={5,3} output:5 1 3 -1 -3 [5 3 6] 7 q={5,6},{6} output:6 1 3 -1 -3 5 [3 6 7] q={6} output:7 ``` 由于每个元素最多入队一次，出队一次（为什么？），所以 时间复杂度为$O(n)$ 当然，这题还可以用ST表和线段树来做，但都没有单调队列 方便 ### 实现： 由于要对队首和队尾进行维护，所以我们需要使用 **双端队列** 可以用STL中的deque，也可以手写 ### 代码：//使用deque ``` #include<bits/stdc++.h> using namespace std; int n,m; int read(){//快读 char ch=getchar(); int f=1; int sum=0; while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar(); return f*sum; } deque<int>q; int a[1000005]; int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){//最小值 while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();//去尾 q.push_back(i); if(i>=m){ while(!q.empty()&&q.front()<=i-m) q.pop_front();//删头 printf("%d ",a[q.front()]); } } printf("\n"); while(!q.empty()) q.pop_front(); for(int i=1;i<=n;i++){//最大值 while(!q.empty()&&a[q.back()]<a[i]) q.pop_back();//去尾 q.push_back(i); if(i>=m){ while(!q.empty()&&q.front()<=i-m) q.pop_front();//删头 printf("%d ",a[q.front()]); } } printf("\n"); return 0; } ``` ### 应用 单调队列是一种小的数据结构，一半不单独出现， 但是经常我们会遇到**单调队列优化的DP** 举例：NOIP 2017 PJ 第四题 [P3957跳房子](https://www.luogu.org/problemnew/show/P3957) 二分+DP+单调队列优化，这里请大家仔细查阅题解 某年NOIP TG 的初赛完善程序 [烽火传递](http://oj.jzxx.net/problem.php?id=2944) 虽然这题你可以用二叉堆，但明显单调队列更好 大家可以看看，这里我就不讲这么多了 感谢阅读！