洛谷P1886滑动窗口模板：单调队列原理与C++实现

1. 题目概述与单调队列的思维起点1.1 这道题到底在考察什么洛谷 P1886 题目全称是“滑动窗口 /【模板】单调队列”它几乎是算法竞赛选手入门“单调队列”这个数据结构的必经之路。很多新手第一次看到这道题会觉得它不过是一个“每次滑一个格子、在窗口里找最大最小值”的暴力题但真正动手写之后才发现暴力写法在数据范围稍大的时候会直接超时而单调队列的精髓恰恰在于把时间复杂度从 O(nk) 压到 O(n)。题面很简单给定一个长度为 n 的数组以及一个大小为 k 的滑动窗口窗口从数组最左端滑到最右端每次向右移动一位要求输出每个窗口内的最大值和最小值。n 和 k 的范围通常可以到 10^6 级别这意味着 O(nk) 的暴力做法铁定过不了必须用线性的思路来解决。这道题之所以被称作“模板题”是因为它把单调队列最核心的“维护候选值”思想完整地展现了一遍。理解这道题就相当于掌握了单调队列的基本骨架后续遇到优化 DP、求区间最值、处理某些双指针问题等场景都能复用同一套思维。1.2 为什么窗口滑动能在线性时间内完成先想想暴力的痛点在哪里窗口每移动一格就要重新扫描 k 个元素找最大最小值做了大量重复比较。当 k 很大时重复扫描的代价极高。单调队列的突破口在于一个朴素观察——窗口向右滑动的过程中很多元素明明已经被比较过一次甚至已经不可能再成为答案却还要被反复扫描。举个例子假设当前窗口内的元素为 [3, 1, 4, 2]要找最大值。从左到右扫过去看到 3记录它是当前的候选看到 1它小于 3暂时不会影响结果看到 4它比 3 和 1 都大那么问题来了既然 4 已经在窗口里而且 4 的位置比 3 和 1 都靠右更晚离开窗口那么 3 和 1 还有必要被保留吗答案是没用了。因为只要 4 还在窗口内最大值就轮不到 3 或 1而 3 和 1 离开窗口的时间早于 4也就是说 4 能“活”得更久覆盖 3、1 的整个剩余生命周期。这个“能活得更久且值更大”的元素可以完全取代之前的候选值。单调队列做的事情就是维持一个“值单调递减或递增、下标单调递增”的候选序列任何不符合这个规则的旧元素直接弹出不需要再回头比较。每个元素最多入队一次、出队一次整体就是 O(n)。1.3 单调队列名字里的“单调”到底是什么意思“单调”指的是队列中元素的某种属性始终保持递增或递减。在 P1886 中我们需要同时维护两个队列一个用来求最小值队列内部元素值单调递增一个用来求最大值队列内部元素值单调递减。但需要注意的是我们比较的不仅仅是值还要结合下标。算法的核心有三件事入队前先弹出队尾那些“又老又没竞争力”的元素入队后把当前元素加到队尾每次移动窗口后检查队头元素是否已经滑出窗口如果滑出则弹出。这三件事的顺序和细节就是本题的全部关键。很多新手会卡在“为什么队头就是答案”这个问题上。其实只要保证队列里的元素下标是单调递增的那么队头元素就是当前窗口内最靠左的候选值。再结合队内值的单调性队头自然就是窗口内的最值。这个逻辑需要反复理解一旦想明白后面的代码就只是机械实现了。2. 核心细节解析与实现准备2.1 C 中双端队列容器的选型实现单调队列有两种常见方式一种是用 C STL 中的 deque双端队列另一种是用普通数组模拟双端队列。对于刚接触单调队列的选手我建议先用 deque 把逻辑跑通因为它的 push_back、pop_back、pop_front、front、back 接口和单调队列的操作一一对应写起来非常直观。deque 的底层虽然看起来是“双端都能操作”但它并不是链表而是分段连续的存储结构随机访问和两端操作都很高效。在 P1886 这种纯模板题里deque 的常数虽然比数组模拟略大但通常也能通过。如果评测机比较严格或者题目数据量特别大再改用数组模拟来压常数。使用 deque 写法的核心代码思路如下#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 1; i n; i) scanf(%d, a[i]); // 求最小值维护单调递增队列 dequeint q; for (int i 1; i n; i) { // 队尾元素大于等于当前值弹出保留更小的 while (!q.empty() a[q.back()] a[i]) q.pop_back(); q.push_back(i); // 队头下标滑出窗口 if (q.front() i - k) q.pop_front(); // 窗口长度达到 k 才开始输出 if (i k) printf(%d , a[q.front()]); } printf(\n); // 清空队列求最大值维护单调递减队列 q.clear(); for (int i 1; i n; i) { while (!q.empty() a[q.back()] a[i]) q.pop_back(); q.push_back(i); if (q.front() i - k) q.pop_front(); if (i k) printf(%d , a[q.front()]); } printf(\n); return 0; }这段代码就是 P1886 的完整 AC 解法。核心操作只有四个队尾弹出、队尾压入、队头过期判断、取队头作为答案。每次循环都只做常数次操作整体线性。2.2 为什么队列里存下标而不是直接存值这是一个非常重要且容易忽略的设计决策。很多新手会不自觉地在队列里直接存元素值然后发现无法判断窗口是否过期。因为判断一个元素是否已经滑出当前窗口必须知道它的原始位置。如果只存值就丢失了位置信息压根没法判定“这个候选值是不是已经不属于当前窗口了”。所以队列里存的必须是数组下标。通过下标既可以拿到元素值a[q.front()]又可以做窗口边界判断q.front() i - k。这也是单调队列和普通栈、普通队列最大的区别之一——它通过下标把“值的大小关系”和“位置的先后关系”绑定在了一起。在窗口滑动的过程中下标的作用还体现在另一处队尾弹出时比较的是 a[q.back()] 和 a[i] 两个值的大小而不是比较下标。因为我们要淘汰的是“值没优势的旧元素”而不是“位置落后的元素”。位置关系是由滑出窗口的判断来负责的两者各司其职互不重叠。2.3 维护单调性的两条关键规则规则一新元素入队前从队尾依次弹出所有“不如新元素”的旧元素。在求最小值时“不如”意味着旧元素的值 ≥ 新元素的值在求最大值时“不如”意味着旧元素的值 ≤ 新元素的值。为什么要这么做因为新元素的下标更大意味着它的生命周期更长一个值更好、活得更久的元素完全有能力覆盖旧元素旧元素就没有存在价值了。规则二窗口滑动后从队头弹出所有下标已经小于等于 i-k 的元素。这里要注意队头元素的特征是下标最旧所以只需要从队头逐个弹出就行。队头弹出的时机可以放在入队操作之后也可以放在取答案之前只要保证取到的队头没有过期即可。这里有一个细节值得强调如果先处理过期元素再入队也可以但处理顺序要统一。我习惯的顺序是“先队尾弹出维护单调性 → 再入队 → 再队头弹出过期元素”这样写逻辑清晰也不容易漏掉边界条件。2.4 代码提交时容易踩的坑第一个坑是数组越界。如果队列存下标而数组下标从 1 开始那么 i-k 有可能小于 1但不会影响 q.front() i-k 的判断因为队头下标最小也是 1而 i-k 可能是负数判断结果必然是 false不会误弹。但如果数组下标从 0 开始边界就要对应调整否则容易差一个位置。第二个坑是输出时机。窗口长度不足 k 时不能输出结果否则会在最开始几个元素处多输出。判断条件 i k 是常见的写法也可以用if (i k)具体要看你的下标起始位置。第三个坑是同时求最大值和最小值时队列要清空且维护单调性的比较符号不要写反。我见过不少人在拷贝代码时把两个循环写成了同样的比较符号结果最大值和最小值输出完全一样这种低级错误在比赛中一旦发生心态很容易崩。3. 实战推演手把手模拟整个滑动过程3.1 用一组测试数据完整走一遍流程设定一个长度为 8 的数组[1, 3, -1, -3, 5, 3, 6, 7]窗口大小 k 3。这是洛谷题目样例我们用它来验证单调队列的实际运行过程。这里只模拟求最小值的单调递增队列。初始化队列为空。i1a[1]1。队尾无元素直接入队。队列状态下标[1]。此时 i3不输出。i2a[2]3。队尾元素 a[1]1因为 1 3不弹出队尾直接入队。队列状态[1, 2]。i3不输出。i3a[3]-1。队尾元素 a[2]33 ≥ -1弹出队尾元素 a[1]11 ≥ -1弹出。队列变为空然后 -1 入队。队列状态[3]。i3输出 a[3] -1即第一个窗口 [1,3,-1] 的最小值。i4a[4]-3。队尾元素 a[3]-1-1 ≥ -3弹出队列为空-3 入队。队列状态[4]。检查队头是否过期q.front()4i-k14 1未过期。输出 a[4] -3窗口 [3,-1,-3] 的最小值。i5a[5]5。队尾元素 a[4]-3-3 5不弹出直接入队。队列状态[4, 5]。队头 4 i-k2未过期。输出 a[4] -3窗口 [-1,-3,5] 的最小值。i6a[6]3。队尾元素 a[5]55 ≥ 3弹出队尾元素 a[4]-3-3 3不弹出3 入队。队列状态[4, 6]。队头 4 i-k3未过期。输出 a[4] -3窗口 [-3,5,3] 的最小值。i7a[7]6。队尾元素 a[6]33 6不弹出直接入队。队列状态[4, 6, 7]。检查队头q.front()4i-k44 ≤ 4说明下标 4 的元素已经滑出窗口弹出。队列状态[6, 7]。输出 a[6] 3窗口 [5,3,6] 的最小值。i8a[8]7。队尾元素 a[7]66 7不弹出直接入队。队列状态[6, 7, 8]。检查队头q.front()6i-k56 5未过期。输出 a[6] 3窗口 [3,6,7] 的最小值。最终最小值序列-1, -3, -3, -3, 3, 3。和题目的预期输出完全一致。通过这组模拟可以直观看到每个元素最多入队一次、出队一次但弹出的时机可能是在队尾因为被更优元素替代也可能是在队头因为滑出窗口两种弹出路径合起来保证了每个下标最多被处理两次。3.2 边界情况窗口大小等于数组长度当 k n 时整个数组就是一个窗口滑动窗口其实没有滑动。这种情况下单调队列的流程会怎样第一个元素入队后续元素逐个入队并维护单调性队头过期判断会等到 i-k 增长到超过队头下标才会触发但数组已经遍历完了。实际运行效果等价于直接对整个数组做一次线性扫描求最值。这反而是最简单的边界情况代码不需要任何特判天然正确。真正容易出错的反而是 k 1 的情况。k 1 时窗口每次只包含一个元素最大值和最小值就是元素本身。单调队列流程中队尾弹出会把前面所有元素弹出因为每个新元素都可能把旧元素替代掉队头过期判断会立即弹出之前的队头因为 i-k 等于上一个下标。最终输出就是原数组。这个边界情况可以帮助你检验代码的队头弹出逻辑是否写对。3.3 数组模拟双端队列的写法与常数优化如果担心 deque 的常数问题或者有些老式评测环境对 STL 支持不够好可以用数组模拟双端队列。原理完全一样只是用两个下标 head 和 tail 来标记队列的有效区间。#include bits/stdc.h using namespace std; const int MAXN 1000005; int a[MAXN]; int q[MAXN]; // 数组模拟队列q[head] 到 q[tail] 为有效区间 int main() { int n, k; scanf(%d%d, n, k); for (int i 1; i n; i) scanf(%d, a[i]); // 求最小值 int head 1, tail 0; for (int i 1; i n; i) { // 队尾弹出tail head 表示队列非空 while (tail head a[q[tail]] a[i]) tail--; q[tail] i; // 队头过期 if (q[head] i - k) head; if (i k) printf(%d , a[q[head]]); } printf(\n); // 求最大值重置队列 head 1; tail 0; for (int i 1; i n; i) { while (tail head a[q[tail]] a[i]) tail--; q[tail] i; if (q[head] i - k) head; if (i k) printf(%d , a[q[head]]); } printf(\n); return 0; }数组模拟的核心就是 tail head 的判断替代了 deque 的 empty()。当 tail head 时队列为空新元素直接放在 q[tail] 位置。这里有一个头尾指针初始化的细节head 初始化为 1tail 初始化为 0这样第一个元素入队时 tail 得到 1和 head 相等表示队列里有一个元素。我自己比赛时更倾向用数组模拟因为心理上觉得 STL 的封装会带来不可控的常数开销。虽然实际差距可能并不大但在 n 达到 10^6、测试点多达几十个的场景下每次循环少一些函数调用累积起来的差别还是很客观的。3.4 快速界定窗口边界用 i 减 k 还是用 i 减 k 再加 1窗口边界的计算是本题最容易混淆的地方。当处理到第 i 个元素时当前窗口覆盖的下标范围是 [i-k1, i]。例如 i5、k3 时窗口下标为 3、4、5。那么一个下标 pos 在窗口内的条件就是 pos i-k因为 i-k1 是最左端下标pos 必须大于等于 i-k1等价于 pos i-k。所以队头过期的判断写成q.front() i-k是完全正确的。如果写成 i-k1也是一样的效果但更容易写错成 i-k那就会差一个元素。我建议死记一个版本队头小于等于 i-k 就弹出不要临场再推。反过来如果我们换一种理解先入队再判断“队头是否小于 i-k1”也就是if (q.front() i-k1) pop_front()效果完全一样。两种写法取决于你更喜欢大于还是小于的判断。选一种固定的写法刷题时就不要再改了能有效减少低级错误。4. 常见问题与调试技巧实录4.1 为什么我的输出总是和答案差一位这个问题的根源几乎都在“窗口长度不足 k 时的输出控制”。如果输出条件写成了if (i k-1)而数组下标从 1 开始那么当 i k-1 时窗口实际只有 k-1 个元素却提前输出了答案自然整体错位。还有一个常见场景是混合使用从 0 开始的下标。如果数组从 0 开始读入那么当处理到下标 i 时当前窗口是 [i-k1, i]最左端是 i-k1而过期判断就变成q.front() i-k1。这和从 1 开始的情况在形式上会有微妙差异。解决办法是统一下标起始我个人的习惯是从 1 开始因为这样边界判断更符合人类直觉。调试时建议先用小规模数据手动模拟一遍比如 n5、k3把每一步的队列内容打印出来。很多题解没有打印这一步但实际做题时我每次卡边界都会在循环里临时加一行输出观察队头和队尾的变化比干瞪眼盯代码效率高得多。4.2 单调队列一写就死循环问题出在哪如果你在 while 循环里忘写了弹出操作或者弹出条件写成了a[q.back()] a[i]而不是在某些数据下可能出现队列里的元素永远不被弹出最终导致死循环或者逻辑错误。这里涉及一个关键细节求最小值时队尾弹出条件是a[q.back()] a[i]还是a[q.back()] a[i]。两者都能维护单调性差别在于相等元素是否会被保留。用会弹出相等的旧元素保留最新的下标用会保留旧下标。两种写法对“是否输出正确最值”没有影响但用可以让队列更短、常数更小。不过要注意如果题目要求输出的是“最靠左/最靠右”的最值那等号的处理方式就会影响结果。P1886 只要求输出值不要求下标所以等号无所谓。死循环的另一个可能原因是数组模拟时 head 和 tail 的初始化不一致。比如 head 初始化为 0、tail 初始化为 0但第一个元素入队时 tail 变成 1head 还是 0判断队列非空的条件 tail head 永远成立逻辑就乱了。4.3 时间超限TLE时如何优化如果你用 deque 写正确了但 TLE优先检查是不是评测环境比较严格或者使用了cin/cout且没有关闭同步。在竞赛环境中建议统一使用scanf/printf或者在使用 cin 时加上ios::sync_with_stdio(false); cin.tie(0);。如果输入输出已经很快还是 TLE那就是 STL 常数问题换成数组模拟即可。另一个隐蔽的常数开销是一次性输出大量数据时用了cout的默认缓冲导致频繁刷新。建议把结果先存入 string 或缓冲区最后一次性输出能省下很多时间。P1886 这种纯模板题一般不会卡 deque 的常数但如果把这道题的模板拿去参加更严苛的比赛数组模拟绝对是一个值得养成的习惯。4.4 单调队列与优先队列、单调栈的区分很多新手会在“单调队列”“单调栈”“优先队列”三个概念之间打转这里我做一个直接对比方便理解为什么选单调队列。数据结构维护方式时间复杂度适用场景单调队列双端操作按值和下标淘汰O(n)滑动窗口区间最值、DP 优化单调栈只在栈顶操作按值淘汰O(n)找左右两侧第一个更大/更小元素优先队列堆结构按优先级取顶O(n log k)需要动态取最值但允许过期元素延迟删除优先队列虽然也能解决滑动窗口最值问题但因为堆里会堆积大量过期元素实际复杂度会退化为 O(n log n) 级别且实现上需要配合懒删除代码复杂度比单调队列高不少。单调栈则完全无法处理“窗口滑动导致旧元素失效”的问题因为它不支持队头删除。三者各有各的用武之地但在 P1886 这个场景下单调队列是唯一的最优解。5. 从 P1886 延伸单调队列在竞赛中的进阶用法5.1 滑动窗口最值问题的一题多解P1886 的模板思路可以直接套用到很多变体题。最典型的是“二维滑动窗口”也就是在一个 n×m 的矩阵中求每个 k×k 子矩阵的最大值或最小值。做法是先在行方向上对每行做一次单调队列得到每行每个窗口的最值再在列方向上对这些结果再做一次单调队列相当于把二维问题拆成两轮一维问题。时间复杂度 O(nm)非常经典。另一个常见变体是“环形数组上的滑动窗口”。把数组复制一份接到原数组后面长度为 2n然后用单调队列处理长度为 k 的窗口就能覆盖所有环形窗口的情况。不过要注意窗口长度不能超过 n否则可能出现同一个元素被重复计入需要特判。5.2 单调队列优化 DP 的核心套路单调队列更大的价值在于优化动态规划。很多 DP 状态转移方程具有如下形式dp[i] max(dp[j] cost(j))其中 j 属于区间 [i-k, i-1]如果直接枚举 j复杂度是 O(nk)。但如果我们把 dp[j] cost(j) 看作一个随 j 变化的“值”那么随着 i 增大合法的 j 区间就像滑动窗口一样向右移动。这时就可以用单调队列维护这个区间内的最大值把转移优化到 O(1)总复杂度降为 O(n)。典型题目如“烽火传递”“修剪草坪”等都是同一类套路。识别这类题目的特征有三个状态转移只依赖一个连续的前缀区间区间长度固定或由题目限制转移方程内层有 max/min 操作。满足这三个特征直接上单调队列。使用单调队列优化 DP 时需要特别注意入队和出队的顺序。通常是先弹出队头过期元素再用队头更新 dp[i]最后把当前 dp[i] 的值入队。因为当前状态不能立即用于更新自身必须等下一轮才生效。如果顺序颠倒会用到还未计算完的状态导致结果错误。5.3 单调队列配合二分答案的经典组合在“最大值最小化”或“最小值最大化”类问题中常常要先二分答案再用单调队列做合法性检查。例如给定一个数组要求分成若干段每段长度不超过 k问每段和的最大值最小是多少。这类问题里二分的是答案上限检查时用 DP 判断是否存在一种划分方式使得每段和都不超过上限而 DP 的转移又可以用单调队列优化。单调队列在这里扮演的角色是“快速获取一段区间内的最优 DP 值”避免每次检查都重新扫描整个数组。二分套单调队列的复杂度通常是 O(n log V)V 是答案值域在竞赛中非常常用。5.4 离线处理多维区间查询的思想迁移单调队列看似只是针对滑动窗口的算法但它的思想可以扩展到“维护一个集合内动态有效的最值”。比如处理某些静态区间查询时可以先把查询按右端点排序然后从左到右扫描数组用单调队列维护当前右端点下所有可能成为答案的候选值。这种离线思路能解决一部分没有修改操作的区间最值问题。不过要提醒一点单调队列只适合处理“窗口移动方向固定”的场景。如果查询的左右端点都是随意变化不能简单转化为单向滑动那就该用线段树或 RMQ 等数据结构硬套单调队列反而会把问题搞复杂。学会判断一道题到底适不适合用单调队列本质上是在判断“候选集合的更新是否满足先进先出的窗口性质”。6. 冲刺阶段的刷题建议与注意事项6.1 P1886 在整个备考计划中的定位我认为 P1886 属于“基础模板题中的必刷题”。它不像数学题那样需要大量推公式也不像大模拟题那样考验代码细节它考察的是一个非常纯粹的数据结构思想。把这道题吃透你就有了一把打开“线性 DP 优化”大门的钥匙。刷题顺序上建议先把单调队列的模板打熟做到 5 分钟内无脑 AC再去碰那些需要套用单调队列的中等题。模板题的意义在于建立肌肉记忆比赛时不需要现场推演直接凭条件反射写出来。如果每次写单调队列都要现场想队列里存什么、弹出条件怎么写考试时心态很容易崩。6.2 如何高效自查代码正确性在洛谷提交代码前我习惯做三件事先跑题目样例再手动构造几组边界数据最后用随机对拍验证。样例是基础边界数据至少要有 n1、k1、kn、数组全相等、数组单调递增、数组单调递减这几类。全相等数组特别能检验等号处理是否得当单调递增数组能检验队尾弹出是否会被频繁触发。随机对拍是竞赛选手几乎必备的技能写一个暴力程序随机生成数据然后对比暴力结果和单调队列结果。如果你的单调队列写错了对拍几乎一定能发现。P1886 作为模板题值得你做一次完整的对拍练习因为对拍本身也是一种比赛技能。6.3 常见提交错误与应对策略汇总我在带新手的过程中总结了一张 P1886 高频错误对照表这里直接分享出来错误现象可能原因解决办法输出结果整体向右偏移一位输出条件i k写成了i k或数组下标从 0 开始却没调整边界统一下标从 1 开始输出条件用i k最大值和最小值输出相同两个循环的比较符号写反了最小值用最大值用弹出队尾运行错误RE数组开小了或队列下标越界数组开到 n5检查 q[head] 是否可能超过 n答案对但超时使用 cin/cout 未关同步或 deque 常数过大改用 scanf/printf 或数组模拟结果缓冲后一次输出这份表格可以贴在笔记里每次刷单调队列题之前扫一眼。比赛中很多错误都是机械性的能快速定位错误类型就能省下大量调试时间。6.4 刷题之外的两个小建议第一强烈建议把 P1886 的模板封装成函数。比如void slidingWindowMin(int a[], int n, int k, int ans[])和void slidingWindowMax(...)平时刷题直接调用比赛时也能减少重复写代码的时间。模板封装得越熟练考场上越从容。第二不要只刷这一道题就觉得自己会了单调队列。我见过很多选手P1886 能 AC但换一道需要自己发现“这里能用单调队列”的题目就懵了。识别模型的能力只能靠多刷不同类型的题来培养。建议在 P1886 之后紧接着刷几道区间 DP 优化题巩固“把内层枚举换成单调队列”的套路。我个人在实际刷题时还有一个习惯每道模板题都会尝试至少两种写法一种是 STL 版本一种是数组模拟版本然后对比两者的时间差距。这个过程能帮你建立起对常数开销的直觉以后遇到时间卡得紧的题时就能准确判断用哪种写法更稳妥。单调队列这道题就是很好的练习对象因为它足够简单你能把注意力完全放在性能对比上而不是被题目本身的逻辑干扰。