单调队列讲解

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

目录

• 从一道题开始
• 单调队列到底是个啥
• 为什么普通 queue 不行？
• 正确的写法：deque + 结构体
• 例题演练：滑动窗口最小值
• 手动模拟过程
• 代码模板
• 复杂度与适用场景
• 总结

从一道题开始

先看一个很经典的题：

给你一个长度为 (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<<' ';}

这个代码有两个大问题：

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

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

正确的写法：deque + 结构体

我们用deque<node>：

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

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

1. 清理元素（队头）
   窗口右边界是i，左边界是i - k + 1。如果队头的下标比左边界还小，说明它已经滑出去了，直接pop_front()。

   while(!q.empty()&&q.front().id<i-k+1)q.pop_front();

2. 从队尾维护单调性
   我们要递增队列，所以只要队尾元素的值大于等于当前新值a[i]，它就再也不可能成为窗口的最小值了，果断pop_back()。

   while(!q.empty()&&q.back().v>=a[i])q.pop_back();

3. 新元素入队
   处理好前面的后，把当前元素{i, a[i]}塞到队尾。

   q.push_back({i,a[i]});

4. 取答案
   当窗口形成以后（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=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<<' ';}}

复杂度与适用场景

• 时间复杂度：每个元素最多入队一次、出队一次，每一步都是 (O(1))，整体(O(n))。
• 空间复杂度：队列里最多存 (k) 个元素，(O(k))。

除了这种裸的滑动窗口极值，单调队列还常用来优化DP，比如“可从前面长度为 (k) 的区间转移”的题目，把转移的 (O(k)) 变成 (O(1))，相当好用。

总结

1. 单调队列的核心就是双端队列维护单调性，存下标、删过期、删无效、取队头。
2. 求最小值用递增队列，求最大值用递减队列，比较符号换一下就行。
3. 一般不用用queue来写，它没有pop_back()，天生残疾。
4. 动手模拟一遍流程，以后遇到这类题基本可以秒。