单调队列看完这篇滑动窗口最小值再也难不住你目录从一道题开始单调队列到底是个啥为什么普通 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;};queuenodeq;for(ll i1;in;i){while(q.size()q.front().idi-k)q.pop();while(q.size()q.front().va[i])q.pop();// 想删掉比新元素大的q.push({i,a[i]});if(ik)coutq.front().v ;}这个代码有两个大问题只能操作队头碰不到队尾第二个while里想删掉所有“比新元素大”的值但queue只能从队头删真正该删的大值往往在队尾根本够不着。单调性维护错位置维护单调递增应该从队尾把那些大的弹出去而不是在队头瞎折腾。所以想写单调队列queue可以直接弃用上deque。正确的写法deque 结构体我们用dequenodestructnode{ll id;// 下标ll v;// 值};dequenodeq;整个算法就四步一步都不能乱清理元素队头窗口右边界是i左边界是i - k 1。如果队头的下标比左边界还小说明它已经滑出去了直接pop_front()。while(!q.empty()q.front().idi-k1)q.pop_front();从队尾维护单调性我们要递增队列所以只要队尾元素的值大于等于当前新值a[i]它就再也不可能成为窗口的最小值了果断pop_back()。while(!q.empty()q.back().va[i])q.pop_back();新元素入队处理好前面的后把当前元素{i, a[i]}塞到队尾。q.push_back({i,a[i]});取答案当窗口形成以后i k队头元素就是当前窗口的最小值直接输出。if(ik)coutq.front().v ;// 输出单个值空格分开注意输出语句里cout和之间可以保留风格我这里为了看得清保留了一个空格实际你的模板里都是连写的coutq.front().v ;也没问题后面例题代码全部统一成紧凑格式。例题演练滑动窗口最小值题目是开头那个完整代码#includebits/stdc.husingnamespacestd;#definerep(i,a,n)for(ll ia;in;i)typedeflonglongll;constintmaxn2e510;structnode{ll id;// 元素在原数组中的下标ll v;// 元素的值};ll a[maxn];dequenodeq;// 双端队列维护单调递增ll n,k;intmain(){cinnk;rep(i,1,n){cina[i];// 1. 弹出窗口外的元素while(!q.empty()q.front().idi-k1)q.pop_front();// 2. 从队尾删掉所有大于等于当前值的元素维持递增while(!q.empty()q.back().va[i])q.pop_back();// 3. 当前元素入队q.push_back({i,a[i]});// 4. 窗口形成输出队头最小值if(ik)coutq.front().v ;}return0;}测试样例输入8 3 4 2 5 1 3 6 2 7输出2 1 1 1 2 2手动模拟过程拿上面的样例一步一步走理解更深刻。队列里展示的是(下标:值)窗口大小k 3。ia[i]操作后的队列递增窗口范围输出14(1:4)[1]-22(2:2)[1,2]-35(2:2) (3:5)[1,2,3]241(4:1)[2,3,4]153(4:1) (5:3)[3,4,5]166(4:1) (5:3) (6:6)[4,5,6]172(4:1) (7:2)[5,6,7]287(4:1) (7:2) (8:7)[6,7,8]2看点细节i2时a[2]2比队尾的4小所以4被弹出只留下2。i4时新值1比队里的5和2都小它俩全被弹走同时队头的(2:2)因为下标2已经小于窗口左边界2也被清掉。最后只剩(4:1)窗口最小值变成1。后面就一直按这个逻辑走非常丝滑。代码模板为了方便以后直接用我把求最小值和最大值的模板都贴出来只改数组名和窗口大小就行。#includebits/stdc.husingnamespacestd;#definerep(i,a,n)for(ll ia;in;i)typedeflonglongll;constintmaxn2e510;structnode{ll id,val;};ll a[maxn];dequenodeq;// 滑动窗口最小值单调递增队列voidsolve_min(ll n,ll k){q.clear();rep(i,1,n){while(!q.empty()q.front().idi-k1)q.pop_front();while(!q.empty()q.back().vala[i])q.pop_back();q.push_back({i,a[i]});if(ik)coutq.front().val ;}}// 滑动窗口最大值把 改成 就行变成递减队列voidsolve_max(ll n,ll k){q.clear();rep(i,1,n){while(!q.empty()q.front().idi-k1)q.pop_front();while(!q.empty()q.back().vala[i])q.pop_back();q.push_back({i,a[i]});if(ik)coutq.front().val ;}}复杂度与适用场景时间复杂度每个元素最多入队一次、出队一次每一步都是 (O(1))整体(O(n))。空间复杂度队列里最多存 (k) 个元素(O(k))。除了这种裸的滑动窗口极值单调队列还常用来优化DP比如“可从前面长度为 (k) 的区间转移”的题目把转移的 (O(k)) 变成 (O(1))相当好用。总结单调队列的核心就是双端队列维护单调性存下标、删过期、删无效、取队头。求最小值用递增队列求最大值用递减队列比较符号换一下就行。一般不用用queue来写它没有pop_back()天生残疾。动手模拟一遍流程以后遇到这类题基本可以秒。