单调队列讲解-育师

单调队列？看完这篇，滑动窗口最小值再也难不住你

从一道题开始

先看一个很经典的题：

给你一个长度为 (n) 的数组，再给一个窗口大小 (k)，窗口从左往右滑，每次输出窗口里的最小值。

比如数组是4 2 5 1 3 6 2 7，(k = 3)，滑动过程长这样：

[4,2,5] → 最小值 2 [2,5,1] → 最小值 1 [5,1,3] → 最小值 1 [1,3,6] → 最小值 1 [3,6,2] → 最小值 2 [6,2,7] → 最小值 2

最后输出2 1 1 1 2 2。

数据范围 (n \le 2\times10^5)，要是每滑一次就把窗口里的数扫一遍找最小值，复杂度 (O(nk))，妥妥超时。这时候就需要一个能快速维护窗口极值的结构——单调队列。

单调队列到底是个啥

名字听着有点唬人，其实很简单。

单调队列就是一个里面的元素值始终保持单调的队列。
比如求最小值，我们让队列从队头到队尾递增，这样队头永远是最小的那个。

它和普通队列最大的不同在于：我们不但能从队头删元素，还可以从队尾删。所以必须用双端队列deque来实现。

另外，队列里我们一般存的是元素的下标（有时候也顺手把值存上），这样既能比较值的大小，又能判断元素是不是已经滑出窗口了。

为什么普通 queue 不行？

我们可能凭感觉写出这种代码，看着好像挺对：

structnode{ll id,v;};queue<node>q;for(ll i=1;i<=n;++i){while(q.size()&&q.front().id<=i-k)q.pop();while(q.size()&&q.front().v>=a[i])q.pop();// 想删掉比新元素大的q.push({i,a[i]});if(i>=k)cout<<q.front().v<<' ';}

这个代码有两个大问题：

只能操作队头，碰不到队尾
第二个while里想删掉所有“比新元素大”的值，但queue只能从队头删，真正该删的大值往往在队尾，根本够不着。
单调性维护错位置
维护单调递增应该从队尾把那些大的弹出去，而不是在队头瞎折腾。

所以想写单调队列，queue可以直接弃用，上deque。

正确的写法：deque + 结构体

我们用deque<node>：

structnode{ll id;// 下标ll v;// 值};deque<node>q;

整个算法就四步，一步都不能乱：

清理元素（队头）
窗口右边界是i，左边界是i - k + 1。如果队头的下标比左边界还小，说明它已经滑出去了，直接pop_front()。
```
while(!q.empty()&&q.front().id<i-k+1)q.pop_front();
```
从队尾维护单调性
我们要递增队列，所以只要队尾元素的值大于等于当前新值a[i]，它就再也不可能成为窗口的最小值了，果断pop_back()。
```
while(!q.empty()&&q.back().v>=a[i])q.pop_back();
```
新元素入队
处理好前面的后，把当前元素{i, a[i]}塞到队尾。
```
q.push_back({i,a[i]});
```
取答案
当窗口形成以后（i >= k），队头元素就是当前窗口的最小值，直接输出。
```
if(i>=k)cout<<q.front().v<<' ';// 输出单个值，空格分开
```

注意：输出语句里cout和<<之间可以保留风格，我这里为了看得清保留了一个空格，实际你的模板里都是连写的cout<<q.front().v<<' ';也没问题，后面例题代码全部统一成紧凑格式。

例题演练：滑动窗口最小值

题目是开头那个，完整代码：

#include<bits/stdc++.h>usingnamespacestd;#definerep(i,a,n)for(ll i=a;i<=n;++i)typedeflonglongll;constintmaxn=2e5+10;structnode{ll id;// 元素在原数组中的下标ll v;// 元素的值};ll a[maxn];deque<node>q;// 双端队列，维护单调递增ll n,k;intmain(){cin>>n>>k;rep(i,1,n){cin>>a[i];// 1. 弹出窗口外的元素while(!q.empty()&&q.front().id<i-k+1)q.pop_front();// 2. 从队尾删掉所有大于等于当前值的元素，维持递增while(!q.empty()&&q.back().v>=a[i])q.pop_back();// 3. 当前元素入队q.push_back({i,a[i]});// 4. 窗口形成，输出队头（最小值）if(i>=k)cout<<q.front().v<<' ';}return0;}

测试样例：

输入：

8 3 4 2 5 1 3 6 2 7

输出：

2 1 1 1 2 2

手动模拟过程

拿上面的样例一步一步走，理解更深刻。
队列里展示的是(下标:值)，窗口大小k = 3。

i	a[i]	操作后的队列（递增）	窗口范围	输出
1	4	(1:4)	[1]	-
2	2	(2:2)	[1,2]	-
3	5	(2:2) (3:5)	[1,2,3]	2
4	1	(4:1)	[2,3,4]	1
5	3	(4:1) (5:3)	[3,4,5]	1
6	6	(4:1) (5:3) (6:6)	[4,5,6]	1
7	2	(4:1) (7:2)	[5,6,7]	2
8	7	(4:1) (7:2) (8:7)	[6,7,8]	2

看点细节：

i=2时，a[2]=2比队尾的4小，所以4被弹出，只留下2。
i=4时，新值1比队里的5和2都小，它俩全被弹走；同时队头的(2:2)因为下标2已经小于窗口左边界（2），也被清掉。最后只剩(4:1)，窗口最小值变成1。
后面就一直按这个逻辑走，非常丝滑。

代码模板

为了方便以后直接用，我把求最小值和最大值的模板都贴出来，只改数组名和窗口大小就行。

#include<bits/stdc++.h>usingnamespacestd;#definerep(i,a,n)for(ll i=a;i<=n;++i)typedeflonglongll;constintmaxn=2e5+10;structnode{ll id,val;};ll a[maxn];deque<node>q;// 滑动窗口最小值（单调递增队列）voidsolve_min(ll n,ll k){q.clear();rep(i,1,n){while(!q.empty()&&q.front().id<i-k+1)q.pop_front();while(!q.empty()&&q.back().val>=a[i])q.pop_back();q.push_back({i,a[i]});if(i>=k)cout<<q.front().val<<' ';}}// 滑动窗口最大值（把 >= 改成 <= 就行，变成递减队列）voidsolve_max(ll n,ll k){q.clear();rep(i,1,n){while(!q.empty()&&q.front().id<i-k+1)q.pop_front();while(!q.empty()&&q.back().val<=a[i])q.pop_back();q.push_back({i,a[i]});if(i>=k)cout<<q.front().val<<' ';}}