企业官网建设流程全解析

洛谷 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-k+1。如果队头元素的下标小于这个左边界，说明它已经不在窗口内，应该弹出。

这段清理代码必须放在取最值之前，并且放在新元素入队之前还是之后有讲究。我的习惯是先清理过期队头，再维护单调性入队，最后取队头作为答案。因为如果先入队再清理，新元素可能被误伤弹出，逻辑上虽然可以规避，但更容易想错。先清理再入队是最不容易出错的顺序。

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]); } deque<int> 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]，k=3，窗口第一次是[6,4,2]，最小值2；滑到第二次变成[4,2,8]，如果队列里只存值3个元素的位置不明，你怎么知道2还在不在窗口里？

存下标则一切清晰：判断过期就看 q.front() 是否小于 i-k+1，取答案就通过下标去查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. 常见错误与排查技巧实录

再简单的模板题，每个人写的时候都会犯不一样的错。我把自己和周围人在这道题上踩过的坑整理成一个速查表，方便你写完代码对照检查。

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-k+1。队头下标小于左边界时，说明过期。当i等于k-1时，左边界正好是0，队头下标不可能小于0，所以第一个窗口没有任何元素过期，可以正常输出。理解了这个推导，你就不需要死记“i-k+1”这个公式，而是能根据场景自己推出来。以后遇到窗口起点不是0的题目，也能举一反三。

4.3 性能坑：STL选择与隐藏的拷贝开销

deque在绝大多数情况下够用，但有一个细节：如果你声明deque ，每次push_back一个int是轻量操作；但如果你不小心声明成deque 或者更糟——deque<pair<int,int>>，频繁push和pop会增加不必要的开销。P1886的数据是int范围，直接用int就好。另外，如果你使用的是vector来模拟，需要提前reserve或者用简单数组，不然push_back动态扩容会带来大量拷贝。

说到排查方法，我强烈建议你在本地写一个暴力的O(nk)版本，用随机数据和小规模n（比如n=10，k=3）对拍，两边输出逐行比较。一旦不一致，打印出每一轮的队列内容，一眼就能看出是过期没清理还是单调性判断写反了。对拍是算法竞赛选手的基本功，比盯着代码空想要高效太多。

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。我把三种方案放在一个表里对比，方便你按需选择。

从竞赛角度，能用单调队列的题，尽量用单调队列，因为n log k在n到1e6、k到1e5时，log k大概17，乘起来1.7e7，通常也能过，但再来几组测试数据或者叠加别的算法模块，就可能超时。而线性算法在高强度竞争中意味着更大的安全边际。从学习角度，multiset思维的代码很“钝”，没法让你深刻理解单调性，所以我建议你即便知道multiset能AC，也坚持用单调队列刷完P1886这个模板。

5.4 循环数组与二维窗口的扩展思考

如果你觉得P1886已经够了，不妨再想两个变体。第一个是循环数组上的滑动窗口：把原数组复制一份接到后面，长度变成2n，再做一次长度为k的滑动窗口。这么做之后，队头过期的判断式还是q.front() < i-k+1，只是i的遍历范围变成2n-1，而原本的n变成了候选区间长度的一半。第二个是二维滑动窗口，比如在一个m行n列的矩阵里，对每个k×k子矩阵求最大值。思路是：先在每一行内用单调队列求出横向滑动窗口最值，得到一个中间矩阵；再对每一列在中间矩阵上做纵向单调队列。这个操作本质上就是“先横向过滤一次，再纵向过滤一次”，复杂度O(mn)，比暴力快一个数量级。这两个变体如果能在脑子里推演通，说明你对单调队列的理解已经远超模板题本身了。

我个人在实际练习中最大的体会是：P1886这类模板题，一定要亲手写三遍。第一遍看着别人的代码抄，搞清楚每句话的含义；第二遍合上代码自己写，卡住了回头看书；第三遍隔几天再写，写完再对拍验证。三遍下来，单调队列的框架就融入你的肌肉记忆了，后面遇到用单调队列优化的题，你会下意识地写出那个while循环，而不是停下来想半天。这也是为什么我总建议备考算法竞赛的朋友，不要贪多图快，先把几十道模板题吃透，比盲目刷300道难题管用得多。P1886值得你花一个晚上慢慢磨，磨透了你就会感谢这种“笨功夫”。