C++滑动窗口最大值：单调队列从原理到实战

这是我这轮C刷题打卡的第19篇。今天要拆的这道题是滑动窗口最大值LeetCode 239在面试里属于较高频的题目而且它背后那个“单调队列”的思路几乎可以平移套用到一整个滑动窗口题型家族。题目描述特别简短给你一个整数数组 nums 和一个大小为 k 的滑动窗口窗口每次向右移动一格要求返回每个窗口内数值的最大值。不少新手第一反应是“每个窗口扫一遍找最大值不就行了”但数据规模一大暴力做法立马超时。这也是为什么这道题值得单独打卡记录。这篇文章会从头梳理完整思路为什么暴力解法不是终点单调队列是怎么一步步设计出来的用C实现时有哪些必须注意的细节以及我在刷题过程中真实踩过的边界条件的坑。无论你是刚开始刷C算法题的新手还是想快速复习滑动窗口套路的人都可以对照着把这道题彻底吃透。1. 读懂题意滑动窗口最大值到底在问什么1.1 题目描述与示例手推先把题目用大白话讲清楚。给定一个数组 nums比如 [1,3,-1,-3,5,3,6,7]再给一个固定大小 k3。窗口最开始覆盖数组前3个元素也就是索引0到2。每次把窗口向右挪一格索引0出去索引3进来再挪一格索引1出去索引4进来。每挪一次都把窗口里这3个数的最大值记下来。最后输出的数组长度是 n-k1。手动推一遍这组数据窗口1[1,3,-1] → 最大值3窗口2[3,-1,-3] → 最大值3窗口3[-1,-3,5] → 最大值5窗口4[-3,5,3] → 最大值5窗口5[5,3,6] → 最大值6窗口6[3,6,7] → 最大值7最终输出就是 [3,3,5,5,6,7]。这里可以看到几个关键事实窗口只前进不回头每次只有最左边一个元素离开、最右边一个元素进来如果某次离开的是当前最大值下一个窗口的最大值就得重新找如果新进来的元素足够大它会立刻成为新窗口的最大值。这些看似废话的观察恰恰是后面单调队列设计的出发点。1.2 暴力解法为什么一定不是终点新手最容易想到的解法外层循环枚举每个窗口起点内层循环从窗口起点扫到起点k找最大值。时间复杂度 O(nk)。如果 n10^5、k10^4最坏情况下要做 10^9 次比较在普通评测机上基本就是 TLE 的下场。有人可能想优化用变量记录当前窗口最大值窗口移动时如果新元素比它大就更新但问题出在最大值滑出窗口的那一刻。你不知道窗口里次大值是谁只能重新扫描一遍整个窗口找最大值。最坏情况完全可以构造出来比如数组是一个递减序列最大值频繁从左侧滑出窗口每移动一次都触发一次重新扫描复杂度还是 O(nk)。所以这道题真正要求的是一趟遍历解决每个元素进窗口、出窗口各一次在常数时间内维护出当前窗口的最大值。这就是单调队列要干的事。2. 单调队列让“过期最大值”自动滚出窗口2.1 用排队候选人的思维理解单调队列想象你是一个窗口管理员手里维护着一个“候选最大值队列”里面只放那些有可能成为当前窗口最大值的元素。队首永远是最有资格当最大值的候选人。当新元素进窗口时规则只有两条新元素从队尾入队前把队尾所有比它小或等于它的元素全部淘汰。因为新元素更大或相等而且比它们更晚过期队尾那些元素从此刻起永远不可能再成为窗口最大值留着只会占位置。窗口左端滑出一个元素时如果这个元素正好是当前队列的队首说明窗口最大值被滑出去了直接弹出队首如果不是队首说明它早就被后面某个更大的元素淘汰了本来就不在队列里根本不需要额外处理。用刚才的例子手推一遍。nums [1,3,-1,-3,5,3,6,7]k 3。处理索引0值1队列空1入队。队列[1]处理索引1值3队尾1 3淘汰13入队。队列[3]处理索引2值-1队尾3 -1-1入队。队列[3,-1]。窗口已满答案是3处理索引3值-3队尾-1 -3-3入队。同时索引0早已被淘汰无需清理。窗口最大值仍为3。队列[3,-1,-3]处理索引4值5从队尾开始-3淘汰、-1淘汰、3也淘汰5入队。队列[5]。答案是5处理索引5值35 33入队。队列[5,3]。答案是5处理索引6值63淘汰、5淘汰6入队。队列[6]。答案是6处理索引7值76淘汰7入队。队列[7]。答案是7这个队列从头到尾永远是非递增的队首最大队尾最小索引从小到大排列。它维护的其实是一个“窗口内所有潜在最大值”的候选名单跟“在窗口内且未被更大元素压制”的元素。2.2 为什么必须用deque两端O(1)操作是硬要求从上面的过程可以看出候选队列需要支持四种操作队尾弹出淘汰较小元素、队尾插入新元素入队、队首弹出最大值滑出窗口、读取队首获取答案。前三个操作都要求常数时间。C 标准库里恰好有一个容器完美匹配这些要求std::deque双向队列。它支持两端的常数时间插入和删除底层是分段连续缓冲区虽然实现比 vector 复杂但对我们使用者来说只管接口。如果用 vectorpop_front 是 O(n)不行用 list两端操作虽然 O(1)但内存分散、常数开销更大而且这道题并不需要 list 的节点稳定性。实际刷题时 deque 是标准答案。我第一次做这题时还想过优先队列。堆确实能维护最大值但堆不方便处理“某个元素滑出窗口”的问题堆顶过期了要等它被弹出才能发现而且堆里没法快速删除任意元素。优先队列需要配合延迟删除复杂度会变成 O(n log n)明显比单调队列复杂常数也更大。单调队列把过期判断从“主动找”变成“被动等”这是它最妙的地方。3. 完整C实现单调队列的落地代码3.1 参考代码带注释的完整实现直接给出我最终 AC 的版本附带完整注释#include vector #include deque using namespace std; class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); dequeint q; // 队列里存的是索引不是值 vectorint ans; ans.reserve(n - k 1); for (int i 0; i n; i) { // 第一步新元素入队前淘汰所有比它小的队尾元素 while (!q.empty() nums[q.back()] nums[i]) { q.pop_back(); } q.push_back(i); // 第二步把已经滑出窗口的队首索引清掉 while (!q.empty() q.front() i - k) { q.pop_front(); } // 第三步窗口完全形成后记录窗口最大值 if (i k - 1) { ans.push_back(nums[q.front()]); } } return ans; } };ans.reserve(n - k 1) 是顺手加上去的提前分配好容量可以避免 vector 反复扩容带来的拷贝开销。刷 LeetCode 时不明显但对性能敏感的场景这是好习惯。3.2 关键逻辑逐行拆解为什么存索引不存值最核心的一点队列里存的是索引不是值。这可能是整道题最容易忽略、也最容易出 bug 的地方。原因有两个。第一窗口滑出时需要精确判断“哪个元素该走”。如果只存值遇到重复元素会分不清谁是谁。比如窗口 [2,2,3]最大值3滑出后窗口变成 [2,2]队里还剩两个2如果存的是值你根本不知道要删哪个2。存索引可以保证每个元素唯一q.front() 是否等于滑出位置一目了然。第二过期判断 q.front() i - k 本身就需要索引参与只看值是无法判断“是否过期”的。再看第一步为什么用 而不是 当新元素等于队尾元素时队尾旧元素同样应该淘汰。旧元素比新元素更早过期而新元素作为最大值相等也算能存活更长时间旧元素此后永远不可能成为窗口最大值留着只会增加队列长度。用 能保证队列里没有冗余的相等元素。第二步的过期条件值得细说。窗口滑动到当前位置 i 时窗口覆盖的索引范围是 [i-k1, i]。所以索引 i-k 的元素都已经在窗口左边界之外必须清掉。很多人纠结为什么不是 q.front() i-k1其实两者完全等价因为整数区间的关系可以去等号边界。我习惯写 i-k因为 i-k 正好是窗口外最后一个位置语义更直白。第三步的时机i k-1 表示窗口已经覆盖了前 k 个元素从这一刻起往后每次移动都要记录答案。这里直接从 i 的角度判断比写 i-k1 0 更直观也避免踩无符号数比较的坑下面会专门说。3.3 复杂度分析与性能实测时间上每个元素最多进队一次、出队一次所以队列操作总数 O(n)遍历数组本身也是 O(n)整体时间复杂度 O(n)。空间上队列里最多同时存在 k 个元素因为队首到队尾的索引跨度不会超过窗口大小超出窗口的早被第二步清掉了空间复杂度 O(k)。我用随机数据简单实测过n10^5、k10^4暴力法在我的机器上要跑一秒多甚至更久单调队列版本基本在1ms级别差距接近千倍。更极端一点n10^6、k10^5暴力法几乎没法用单调队列仍然毫秒级。这也是为什么 O(nk) 到 O(n) 这道坎在刷题里是决定性的。4. 实战中的坑边界、索引与编译器配置4.1 三个最容易写错的边界条件边界条件这种东西没踩过坑之前总觉得“不就几个 if 吗”踩过之后才知道全在细节里。k1 的情况。窗口就一个元素答案就是原数组本身。用上面的代码跑一遍每个 i 进来第一步会把前一个元素淘汰push i第二步 q.front() i-1 会把前一个索引清走第三步 i 0 直接输出 nums[i]。输出结果正好是原数组逻辑完全自洽。kn 的情况。整个数组只有一个窗口正确答案是数组的全局最大值。代码里第二步的过期条件是 i-k只有当 in-1 时 i-k 才等于0之前的索引不会被清走第三步只在最后一个元素处输出一次此时队首正好是全局最大值。n0 或 kn 的情况。按题目数据范围可能不会出现但严谨起见应该在函数开头加防御逻辑if (nums.empty() || k n) return {};k 为0也可以直接返回空防御性写法能避免线上用例莫名其妙踹你一脚。刷题代码可以省略但工程习惯会提醒你写上。4.2 排查实录size_t下溢与重复值误删这里分享一个我亲眼见过很多次的坑很多人写循环判断时喜欢用 nums.size() 而不是先保存 n。比如for (int i 0; i nums.size() - k 1; i)当 k 大于 nums.size() 时nums.size() - k 1 是 size_t 类型无符号数减法会先发生下溢变成一个巨大的正数结果就是循环直接变成无意义的长跑要么超时要么越界访问。这是 C 里比边界条件更隐蔽的坑因为本地编译不报错甚至小数据量都不触发一提交就莫名其妙 WA 或 RE。我的建议很朴素函数开头写 int n nums.size()后面所有下标和循环全部用 int。刷题场景的数据规模一般不会超过 int 范围这样做从根源上避开无符号数参与算术的隐患。重复值误删这个问题我在 3.2 里已经解释过原理。第一次提交时我存的就是值遇到 [2,2,3] 这种用例直接挂。当时调试了很久才反应过来不是算法逻辑错而是队列里根本没法区分两个相同的2。改成存索引后这道题再也没在重复值上出过问题。如果你已经写过一版存值的版本可以自己跑一下这个用例体会会很深。4.3 顺手解决VS Code的IntelliSense报红刷题打卡时很多人用 VS Code最烦的就是代码能编译通过编辑器里却红波浪线不断。最典型的就是“vscode cpp头文件错误报红”这通常不是代码问题而是 IntelliSense 没找到 C 标准库头文件的路径。最简单的处理有两种。一是如果你的编译器是 g在 .vscode/c_cpp_properties.json 里配置 compilerPath 指向 g 的绝对路径并把 includePath 加上编译器自带的 include 目录。配置参考长这样{ configurations: [ { name: Win32, includePath: [ ${workspaceFolder}/**, C:/Program Files/mingw-w64/include/c/** ], compilerPath: C:/Program Files/mingw-w64/bin/g.exe, cppStandard: c17, intelliSenseMode: windows-gcc-x64 } ], version: 4 }二是如果你跟我一样刷题时不想折腾编辑器配置直接在设置里把波浪线关了C_Cpp.errorSquiggles 设为 disabled。反正代码对不对最终以编译器运行结果为准IntelliSense 的波浪线只是参考没必要让它影响心情。运行编译时我一般用这个命令简单直接g -stdc17 -O2 -o main main.cpp ./main-O2 优化在刷题验证算法性能时比较接近评测机的真实表现。5. 从这题看滑动窗口题型的通用套路与打卡复盘5.1 滑动窗口题型的通用三板斧这道题做完最大的收获是能抽象出滑动窗口类题目的通用思路。我总结成三步几乎可以套用到绝大多数滑动窗口题。第一想清楚窗口的扩张和收缩规则。每次移动过程中哪些元素进窗口、哪些元素出窗口是决定算法正确性的基础。第二决定用什么数据结构维护当前窗口的“状态”。这个状态可以是最大值单调队列、最小值还是单调队列、字符种类数哈希表双指针、区间和前缀和等等。第三确定结果收集的时机通常是在窗口第一次完整形成之后每次移动都记录一次。举两个可以直接套这个思路的题目。LeetCode 3 最长无重复子串双指针维护窗口哈希表记录字符出现次数右指针扩张、左指针收缩每次移动都更新答案。LeetCode 1438 绝对差不超过限制的最长连续子数组需要同时知道窗口最大值和最小值用两个单调队列分别维护右指针扩张窗口左指针在最大最小差超限时收缩。这两个题本质上都是“窗口状态维护”的变体理解了239再写这两道会顺手很多。5.2 打卡复盘19天记录让我学到了什么最后聊聊打卡这件事本身。我的每篇记录里固定写三块内容题目复述和我自己的第一反应、最终 AC 代码、踩坑笔记。今天回看第19篇最有价值的其实不是 AC 代码本身而是那些错误提交记录。比如这道题我第一次用值存储在重复元素用例上挂了三个测试点后来凡是单调队列题型我写代码前都会先问自己一句队列里应该存索引还是存值这个习惯就是靠记录养成的不把每次错误记下来下次遇到类似的坑还是会在同一个地方摔倒。如果你也在做类似的刷题打卡我建议别只贴代码至少写一句“为什么这么写”。不用写得多漂亮哪怕只是“因为存值会误删”这六个字三个月后回看都会很有价值。记录的意义从来不是给别人看是给未来的自己留一条捷径。我的下一道题打算继续做滑动窗口的变种到时候再来更新新的打卡记录。