滑动窗口与单调队列：从洛谷P1886到算法竞赛终极模板

洛谷 P1886 滑动窗口 /【模板】单调队列在算法竞赛圈子里算一道绕不开的必刷题。它的地位有点像练字时的“永”字——题目本身不复杂但把单调队列这个数据结构的核心操作全部浓缩在一个场景里你把它彻底吃透之后再去碰那些所谓“套模板”的进阶题就会顺很多。我刷题这些年见过不少选手在这道题上翻车也见过有人把单调队列和普通队列混为一谈其实两者差着十万八千里。这篇文章我就把P1886从原理到代码到坑点一次讲清楚给正在备战算法竞赛、或者刚看完C基础语法想往数据结构进阶的朋友一份能直接照做的参考。1. 题目到底在考什么滑动窗口与单调队列的关系很多人第一眼看到“单调队列”这四个字会下意识觉得它是一个标准库里现成的容器。实际上C的STL里并没有叫“单调队列”的东西它更像是一种基于双端队列deque实现的思想。P1886的核心场景是给定一个长度为n的数组有一个长度为k的窗口从左往右滑动要求依次输出每个窗口内的最大值和最小值。这个需求用暴力解法做每个窗口内排序或扫描一遍时间复杂度是O(nk)当n和k都到1e5甚至1e6级别时必然超时。单调队列的意义就是让每个元素最多入队一次、出队一次把总时间复杂度压到O(n)。1.1 滑动窗口问题的本质滑动窗口问题说白了就是一句话在一段连续移动的区间里高效维护我们需要的信息。比如区间最大值、最小值、区间和、区间众数等等。P1886只要求最值但“区间 滑动”这个结构在后续很多题目里都会反复出现像字符串匹配、数据流统计、图像处理里的卷积窗口本质上都有滑动窗口的影子。窗口本身是一个长度固定的区间每次向右移动一格左边出去一个元素右边进来一个元素。如果窗口里的元素还有顺序性要求比如最值、单调性判断那么用一个普通队列是远远不够的。普通队列只能保证先进先出你没法快速知道队列里当前最小的元素是多少。这时就需要额外设计一种数据结构让队列内部的元素保持某种有序性这就是“单调队列”的雏形。1.2 为什么队列能维护窗口队列这个结构天然适合窗口因为窗口滑动的方向是单向的左边出的元素正好对应队头右边进的元素正好对应队尾。这是队列能上场的最直观理由。但光有队列还不够关键问题是如何在每次窗口滑动之后快速拿到最值一个朴素想法是维护一个优先队列堆每次取堆顶就能拿到最值但堆的删除操作有问题——窗口左端出去的元素可能不是堆顶想删掉任意元素需要额外标记或懒删除复杂度就上去了。另一个更朴素的思路是维护一个multiset支持O(log k)插入删除和O(1)获取最值这样总复杂度是O(n log k)对于大部分题目已经能过。但既然题目叫“模板”就说明存在更优的线性做法。单调队列的思路很巧妙在入队的时候就把未来“不可能成为最值”的元素提前淘汰掉。比如我们要求窗口最小值当新元素a[i]入队时如果队尾的元素比a[i]还大那么这个队尾元素在窗口内永远不会比a[i]更优因为a[i]更小且更晚过期。所以直接把队尾元素弹出直到队尾元素小于等于a[i]再入队。这样队列里永远保持一个单调递增的序列队头就是当前窗口的最小值。整个过程每个元素最多被弹出一次均摊O(1)操作。2. 单调队列核心操作拆解既然要用单调队列就得先明白它为什么是“双端”的。普通队列只允许队头出队、队尾入队而单调队列还需要在队尾弹出不单调的元素因此必须支持两端操作。这就是为什么C里我们用deque而不是queue来实现单调队列。2.1 双端队列deque为什么会出现在这里deque即双端队列可以在头部和尾部都进行插入删除操作。在实现单调队列时我们需要的操作是队尾入队、队尾弹出不合适的元素、队头弹出过期元素。三个操作里有两个发生在“两端”普通queue根本做不到队尾弹出所以deque成了最自然的工具。STL里的deque底层通常是一段一段的连续空间用中控器管理随机访问虽然不如vector快但两端插入删除是常数时间。对于我们的场景只用到两端操作性能完全够用。如果你在用Dev-C或VS Code配好的C环境直接#include 就能用。2.2 入队时的单调性维护弹出队尾的时机这里以维护窗口最小值为例。我们维护一个单调递增队列队头是最小值。当新元素a[i]准备入队时执行一条循环while (!dq.empty() a[dq.back()] a[i]) dq.pop_back()。意思很明确只要队尾元素对应的数组值不小于当前值队尾就永久失去作为“最小值候选人”的资格。为什么说“永久失去”因为队列里存的是下标窗口滑动时下标更小的元素会更早滑出窗口。新来的a[i]既比队尾元素小或等于又比队尾元素晚过期所以无论在“值”上还是“存活时间”上新元素都全面占优。既然队尾元素永远不可能被选为最小值留着它只会拖慢后续比较直接弹掉即可。这是整个单调队列思想最核心的一句务必理解透彻。这里还有一个细节判断条件用 还是 。如果用 那么相等的元素不会被弹出队列里可能存在两个值相等的不同下标。结果上不会错因为相等值取谁都一样但队列长度会变长操作变多。用 会更激进一点弹出相等元素队列更短性能略好而且不影响正确性所以模板代码里通常写 。2.3 窗口滑动的过期清理队头什么时候该走队列维护的是当前窗口内的元素但窗口会右移所以队头的下标可能已经滑出窗口左边界了。什么时候算“滑出”假设窗口长度为k当前处理到下标i窗口左边界是i-k1。如果队头元素的下标小于这个左边界说明它已经不在窗口内应该弹出。这段清理代码必须放在取最值之前并且放在新元素入队之前还是之后有讲究。我的习惯是先清理过期队头再维护单调性入队最后取队头作为答案。因为如果先入队再清理新元素可能被误伤弹出逻辑上虽然可以规避但更容易想错。先清理再入队是最不容易出错的顺序。3. 全套AC代码与关键行解析看完原理直接上代码。这里我给出两个版本STL deque版本适合快速实现和比赛时减少代码量手写数组模拟版本适合对常数要求高、或者想要更底层掌控的选手。两种写法在P1886上都能通过区别主要在常量和可读性。3.1 STL deque版本5分钟速成写法#include bits/stdc.h using namespace std; const int MAXN 1000005; int a[MAXN]; int main() { int n, k; scanf(%d%d, n, k); for (int i 0; i n; i) { scanf(%d, a[i]); } dequeint q; // 求每个窗口最小值 for (int i 0; i n; i) { // 队头过期清理 while (!q.empty() q.front() i - k 1) { q.pop_front(); } // 维护单调递增 while (!q.empty() a[q.back()] a[i]) { q.pop_back(); } q.push_back(i); // 窗口满后开始输出 if (i k - 1) { printf(%d , a[q.front()]); } } printf(\n); q.clear(); // 求每个窗口最大值维护单调递减 for (int i 0; i n; i) { while (!q.empty() q.front() i - k 1) { q.pop_front(); } while (!q.empty() a[q.back()] a[i]) { q.pop_back(); } q.push_back(i); if (i k - 1) { printf(%d , a[q.front()]); } } printf(\n); return 0; }这个代码逻辑很直白先跑一遍最小值再跑一遍最大值。两次遍历都是O(n)总复杂度O(n)。注意这里队列里存的是下标而不是值因为需要靠下标判断过期这是整段代码里最容易被忽略却最关键的设计。3.2 手写数组模拟卡常选手的优选方案STL的deque确实方便但如果你在比赛中遇到n到1e6、并且题目还叠加了很多其他操作deque的常数可能会让你不太舒服。这时候可以手写数组模拟双端队列代码量也不多。#include bits/stdc.h using namespace std; const int MAXN 1000005; int a[MAXN], q[MAXN]; int main() { int n, k; scanf(%d%d, n, k); for (int i 0; i n; i) { scanf(%d, a[i]); } // 求最小值 int head 0, tail 0; // [head, tail) 左闭右开 for (int i 0; i n; i) { while (head tail q[head] i - k 1) { head; } while (head tail a[q[tail - 1]] a[i]) { tail--; } q[tail] i; if (i k - 1) { printf(%d , a[q[head]]); } } printf(\n); // 求最大值 head 0, tail 0; for (int i 0; i n; i) { while (head tail q[head] i - k 1) { head; } while (head tail a[q[tail - 1]] a[i]) { tail--; } q[tail] i; if (i k - 1) { printf(%d , a[q[head]]); } } printf(\n); return 0; }手写数组的核心思路是用head和tail两个指针维护区间[head, tail)tail指向下一个可写入位置。弹出队头就是head弹出队尾就是tail--。每个元素最多被head和tail各经过一次所以总操作次数是O(n)。这个写法比deque少了STL底层函数的调用开销在极限数据下性能更好。3.3 关于“存下标还是存值”这个关键决策我第一次写单调队列的时候下意识在队列里存了值而不是下标结果写完一跑就发现窗口滑两下就全乱了。原因很简单存值的话你根本不知道队列里的这个值还在不在当前窗口内。比如数组[6, 4, 2, 8, 3]k3窗口第一次是[6,4,2]最小值2滑到第二次变成[4,2,8]如果队列里只存值3个元素的位置不明你怎么知道2还在不在窗口里存下标则一切清晰判断过期就看 q.front() 是否小于 i-k1取答案就通过下标去查a数组。这也是为什么前面两版代码里队列元素类型都是int下标而不是int值——类型一样语义完全不同。这是我在最开始学这道题时踩得最深的坑写出来给各位提个醒。3.4 输入输出处理关同步和用scanf的必要性P1886的数据范围最大到1e6如果用cin/cout且不关同步很可能稳稳地超时。我的建议是要么统一用scanf/printf要么在main开头写ios::sync_with_stdio(false); cin.tie(0);。这两个操作的本质是让C标准输入输出不再和C标准库同步减少底层开销。实际测试中1e6级别的输入用关同步的cin和scanf差距不大但如果你的编译环境或评测机比较老scanf更保险。另外题目的输出是两行每行结尾有换行记得补上printf(\n)多一个空格没关系少换行会WA。4. 常见错误与排查技巧实录再简单的模板题每个人写的时候都会犯不一样的错。我把自己和周围人在这道题上踩过的坑整理成一个速查表方便你写完代码对照检查。错误表现根本原因解决办法输出的第一组窗口结果不对输出时机写成了 i k 而不是 i k-1数组下标从0开始第k-1个位置已经形成满窗口答案偏大或偏小队列里存值而不是下标改为存下标通过下标查值和判断过期超时没有关同步、或用了vector手写存储用scanf/printf、或关cin同步、或数组模拟窗口滑动后结果不更新队头过期清理放在维护单调性之后先清过期队头再维护单调性和入队最大值和最小值反了两个循环的 和 写反求最小值维护递增队列求最大值维护递减队列用了STL queue编译报错queue不支持pop_back换成deque或手写数组模拟双端操作4.1 输出时机提前或延后一拍的经典错误这是一个非常隐蔽的小错误。代码里我写的是 if (i k - 1) 才开始输出。很多初学者写成 i k导致窗口从第二个位置才开始输出第一个窗口被跳过整体答案全部错位一位。数组下标从0开始当i等于k-1时区间[0, k-1]正好有k个元素已经是完整窗口。因此从i等于k-1开始之后每个位置都要输出。这个问题看起来小但排查起来会让人怀疑人生因为样例输出的第一行可能就少了一个数字。4.2 边界条件里的“k-1”到底怎么来的边界判断要不要写等号、要不要减一这种问题统称为“差一错误”。我们已知当前处理到下标i窗口长度为k那么窗口左边界就是i-k1。队头下标小于左边界时说明过期。当i等于k-1时左边界正好是0队头下标不可能小于0所以第一个窗口没有任何元素过期可以正常输出。理解了这个推导你就不需要死记“i-k1”这个公式而是能根据场景自己推出来。以后遇到窗口起点不是0的题目也能举一反三。4.3 性能坑STL选择与隐藏的拷贝开销deque在绝大多数情况下够用但有一个细节如果你声明deque 每次push_back一个int是轻量操作但如果你不小心声明成deque 或者更糟——dequepairint,int频繁push和pop会增加不必要的开销。P1886的数据是int范围直接用int就好。另外如果你使用的是vector来模拟需要提前reserve或者用简单数组不然push_back动态扩容会带来大量拷贝。说到排查方法我强烈建议你在本地写一个暴力的O(nk)版本用随机数据和小规模n比如n10k3对拍两边输出逐行比较。一旦不一致打印出每一轮的队列内容一眼就能看出是过期没清理还是单调性判断写反了。对拍是算法竞赛选手的基本功比盯着代码空想要高效太多。5. 单调队列的进阶玩法从模板题到实战题很多人刷完P1886之后就把单调队列丢到一边觉得“哦这个题会了”。其实单调队列的真正威力体现在两个方向的扩展一是数学形态上的变形比如环形数组、二维滑动窗口二是与其他算法结合最常见的就是动态规划的状态转移优化。5.1 多重背包优化的底层逻辑多重背包问题里如果枚举物品数量时间复杂度是O(n * V * k)其中k是物品个数V是背包容量。用单调队列优化后可以降到O(n * V)这里面的关键就是对于每个余数类同余于某个模数的容量下标转移来源是一个滑动窗口。dp[j] max(dp[j], dp[j - c] w, dp[j - 2c] 2w, ...)展开之后你会发现随着j增大候选集合恰好是“往前数固定步长”的序列而窗口长度由物品数量上限决定。这不就是P1886里的滑动窗口最值问题吗理解了P1886再去看多重背包优化的代码你会恍然大悟原来模板题里的队列、过期判断、单调性维护原封不动地搬到了DP转移里只不过数组值和下标含义换了一下。这也是为什么要先刷模板题、再刷应用题的底层逻辑——模板题是地基应用题是楼。5.2 状态转移DP中的单调队列切入时机形如 dp[i] max/min( dp[j] cost(i, j) ) 的递推式如果j的取值范围随i单调移动并且cost能拆成f(i)和g(j)两项之和就可以用单调队列优化。典型例子是烽火台传递、最大子段和变种、区间分组等。切入时机是你发现暴力转移是两层循环内层j的区间是一个固定窗口或者是一个随i单调平移的区间就可以考虑单调队列。怎么判断“区间是否随i单调平移”一个简单的鉴别方法把j的取值范围写成[l_i, r_i]如果l_i和r_i都不递减也就是左边界和右边界都只往右走那么恭喜单调队列基本适用。这个结论可以直接记实战中非常有用。5.3 单调队列与multiset的选型对比有一部分选手在写滑动窗口最值类题目时会用multiset或者优先队列加懒删除来做也能AC。我把三种方案放在一个表里对比方便你按需选择。方案单次操作复杂度总复杂度优缺点暴力扫描O(k)O(nk)实现简单但数据一大必死multisetO(log k)O(n log k)实现容易支持任意删除但常数大单调队列均摊O(1)O(n)理论最优常数小但对逻辑要求略高从竞赛角度能用单调队列的题尽量用单调队列因为n log k在n到1e6、k到1e5时log k大概17乘起来1.7e7通常也能过但再来几组测试数据或者叠加别的算法模块就可能超时。而线性算法在高强度竞争中意味着更大的安全边际。从学习角度multiset思维的代码很“钝”没法让你深刻理解单调性所以我建议你即便知道multiset能AC也坚持用单调队列刷完P1886这个模板。5.4 循环数组与二维窗口的扩展思考如果你觉得P1886已经够了不妨再想两个变体。第一个是循环数组上的滑动窗口把原数组复制一份接到后面长度变成2n再做一次长度为k的滑动窗口。这么做之后队头过期的判断式还是q.front() i-k1只是i的遍历范围变成2n-1而原本的n变成了候选区间长度的一半。第二个是二维滑动窗口比如在一个m行n列的矩阵里对每个k×k子矩阵求最大值。思路是先在每一行内用单调队列求出横向滑动窗口最值得到一个中间矩阵再对每一列在中间矩阵上做纵向单调队列。这个操作本质上就是“先横向过滤一次再纵向过滤一次”复杂度O(mn)比暴力快一个数量级。这两个变体如果能在脑子里推演通说明你对单调队列的理解已经远超模板题本身了。我个人在实际练习中最大的体会是P1886这类模板题一定要亲手写三遍。第一遍看着别人的代码抄搞清楚每句话的含义第二遍合上代码自己写卡住了回头看书第三遍隔几天再写写完再对拍验证。三遍下来单调队列的框架就融入你的肌肉记忆了后面遇到用单调队列优化的题你会下意识地写出那个while循环而不是停下来想半天。这也是为什么我总建议备考算法竞赛的朋友不要贪多图快先把几十道模板题吃透比盲目刷300道难题管用得多。P1886值得你花一个晚上慢慢磨磨透了你就会感谢这种“笨功夫”。