前几天有朋友问我LeetCode 239 这道滑动窗口最大值到底该怎么优化正好我刷题打卡进行到第 19 期就拿它当这一篇的内容。题目给你一个整数数组nums和一个固定大小的窗口k窗口每次往右滑一步把窗口里的最大值输出成一个新数组。很多新手第一反应是写一个双层循环直接求等n一上10^5就开始卡死。C 刷题党必备的单调队列就是解决它的经典武器。这篇文章我会从暴力解开始一步步推导到基于deque的最优解再把手写队列、优先队列和multiset这些变体都过一遍最后聊聊我在 vscode 里调 C 时遇到的 IntelliSense 头文件报红的坑。如果你正在准备算法面试这题建议至少把单调队列写法掌握到能默写的程度。1. 题目解析与思路拆解1.1 先看懂题意窗口是怎么滑的题目描述很简短但有不少人一开始会绕晕。假设nums [1,3,-1,-3,5,3,6,7]k 3。窗口初始覆盖下标0,1,2也就是[1,3,-1]最大值是3接着窗口右移一格覆盖[3,-1,-3]最大值还是3再右移一格覆盖[-1,-3,5]最大值变成5。最终输出一个长度为n - k 1的数组。这个定义不复杂但你要注意到两个关键点。第一每次窗口只移动一个位置所以相邻两个窗口有k - 1个元素是重叠的。第二窗口是先进先出的结构左侧弹出旧元素右侧加入新元素这种结构天然适合某种队列来维护。题目要求的不是每个窗口的所有元素而是“最大值”所以我们要维护的并不是窗口本身而是一个能快速回答“当前窗口最大值”的数据结构。很多人上来会想用堆因为堆能快速拿到最大值。但这里的难点在于旧元素会离开窗口堆不支持高效删除任意元素除非用懒删除。这就是单调队列要登场的原因它是专门为这种滑来滑去的区间最值问题设计的。1.2 暴力解法的问题到底出在哪先看最朴素的实现vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; for (int i 0; i k nums.size(); i) { int mx INT_MIN; for (int j i; j i k; j) { mx max(mx, nums[j]); } res.push_back(mx); } return res; }外层循环有n - k 1次内层循环每次遍历k个数总复杂度是O(n * k)。当n 1e5、k 1e5时这个数字接近1e10任何 OJ 都扛不住。暴力的问题在于重复比较窗口右移一位后新的窗口里有k - 1个元素和上一个窗口完全一样但暴力的做法把这些元素全部重新比了一遍。换句话说这k - 1个元素的相对关系明明在上一个窗口里已经算过了却没有被好好利用。我们需要一种能继承历史信息的数据结构让新窗口的答案能在常数时间内算出来。最自然的思路是维护一个“候选最大值”的集合随着窗口滑动淘汰掉不可能再成为最大值的元素再引入新元素。单调队列正是这种思路的工程化实现。1.3 为什么单调队列是最优解单调队列的核心思想是队列里的元素按值的大小保持单调递减队首永远是当前窗口的最大值。每次窗口滑动时新元素从队尾入队入队前把所有比它小或等于它的元素从队尾弹出因为那些元素在新元素面前已经“没有出头之日”了。打个比方。你站在一列队伍里前面有一个高个子挡着你你看不到他前面的人但后面来的人可能比你高、也可能比你矮。如果新来的人比队伍末尾的人高那末尾的人在他面前永远被挡住没必要继续留在队伍里如果新来的人矮那他可以排在后面等前面高个子一个个离开后他还有机会成为队首。单调队列就是这样队列里保留的永远是“在当前窗口内按照下标顺序看单调递减的那些值”。每个元素最多进队一次、出队一次所以总复杂度是O(n)。空间上队列中最多同时存在k个元素也就是O(k)。这也是理论上能做到的最优复杂度因为至少要遍历一遍数组不可能低于O(n)。2. 核心细节解析与实操要点2.1 队列里存的是下标不是值这是我最初写这题时最容易忽略的点。很多人的第一版代码很可能是这样的dequeint q; q.push_back(nums[i]); // 存值看起来没毛病等到窗口要判断旧元素是否过期时就尴尬了你只知道队列里有一个旧值但不知道它对应的下标是否已经滑出窗口。举个简单的例子窗口大小k 3队列里存了值7但这个7可能来自十个下标之前早就该被淘汰了你却无从判断。正确做法是队列里存下标需要通过下标访问值时再写成nums[q.front()]。存下标有两大好处一是判断过期非常直观队首下标 i - k就说明它已经离开当前窗口二是如果两个元素值相同我们可以通过下标知道哪个更新更新那个更有保留价值。记住这一点后面很多边界问题都能避免。2.2 三个关键动作的执行顺序单调队列虽然概念简单但执行顺序搞错就会出现诡异的结果。标准流程分三步新元素入队前从队尾开始弹出所有 nums[i]的元素。把当前下标i从队尾入队。检查队首下标是否过期如果q.front() i - k弹出队首。当窗口已经形成也就是i k - 1时记录nums[q.front()]作为答案。这个顺序看起来简单但值得多说一句。为什么不先检查过期再弹出队尾其实两种顺序最终都不会出错但先弹出队尾有一个额外效果如果新元素非常大它可能会把已经过期的队首也一起弹出因为队尾弹出的过程会一直往前清直到遇到比新元素大的元素或者队列为空。这样后续的过期检查就多了一层保障。不过为了逻辑统一我建议还是按上面的三步走不容易乱。还有一个细节是“弹出所有小于等于”而不是“小于”。如果你只弹小于当前值的元素等于当前值的旧元素会留在队里结果不会错但队列会变得不够“精简”。后面单独讲这个坑。2.3 小于等于还是小于聊一下多数人忽略的细节面试时如果被问到和的区别能答上来会加分不少。看一个例子nums [3,3,2]k 2。如果写nums[q.back()] nums[i]也就是只弹出严格小于的i0队列[0]。i1nums[0] 3不小于3所以不弹队列变成[0,1]记录最大值3。i2nums[2] 2队尾nums[1] 3不弹入队[0,1,2]。检查队首0 0弹出队列变成[1,2]记录最大值3。结果正确。如果写i0队列[0]。i1nums[0] 3 3弹出0入队[1]记录最大值3。i2入队[1,2]记录最大值3。结果也正确。那为什么要用因为相等情况下下标更大的元素“寿命”更长。比如[1,3]这两个下标对应的值都是 3旧的下标 1 会在更早时候滑出窗口而新的下标 2 还能多撑一个窗口。用把旧元素弹掉队列更短处理更干净。两种写法在大部分题目里都能过但用是更符合“单调队列只保留未来有机会成为最大值元素”这一理念的选择。2.4 时间与空间复杂度摊还分析的直觉很多初学者看到while循环会担心最坏情况下一个新元素把队列里所有元素都弹出那不是O(k)吗别急这里要用摊还分析来看。每个元素只会被弹出一次一旦弹出就再也不会回来了。所以虽然某一次操作可能弹出k个元素但整个算法过程中弹出的总次数不超过入队总次数n。把n次操作平摊到每个元素上均摊复杂度就是O(1)整体是O(n)。空间方面队列里存的是当前窗口内有资格成为最大值的下标。理论上单调递减队列最多装下整个窗口的所有k个元素比如原数组严格递减时所以空间是O(k)。这个复杂度是这种题目的天花板因为必须扫一遍所有元素所以时间不可能低于O(n)。3. 实操过程与核心环节实现3.1 基于 deque 的标准 C 实现直接给出完整代码建议先照着敲一遍再闭眼睛自己写一遍vectorint maxSlidingWindow(vectorint nums, int k) { dequeint q; // 存下标 vectorint res; res.reserve(nums.size() - k 1); for (int i 0; i nums.size(); i) { // 1. 清掉队尾所有小于等于当前值的元素 while (!q.empty() nums[q.back()] nums[i]) { q.pop_back(); } // 2. 当前下标入队 q.push_back(i); // 3. 队首下标过期就弹出 if (q.front() i - k) { q.pop_front(); } // 4. 窗口满了就记录答案 if (i k - 1) { res.push_back(nums[q.front()]); } } return res; }代码里有一处res.reserve(nums.size() - k 1)这是个小优化。如果你提前知道答案数组大小顺手 reserve 一下能减少 vector 扩容时的多次内存分配。在这个例子里nums.size()是size_t类型减k后可能得到无符号数严格说最好转成int或者直接用n - k 1。不过刷题时一般注意一下类型转换就行。第 3 步用而不是去判断过期也是习惯问题。因为窗口每次只滑动一位所以实际上每次最多只有一个下标会过期用完全等价。但写成更稳健哪怕将来处理窗口跳跃的情况也不会出错。3.2 手写双端队列在 OJ 上更稳的替代std::deque在大多数情况下够用但如果你追求极致性能或者遇到 POJ 那样对常数极度敏感的老题目可以考虑用数组模拟双端队列。实现思路不复杂开一个长度为n的vectorint用head和tail两个指针维护队列区间其中tail指向队尾下一个空位区间[head, tail)是队内元素。vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint q(n), res; res.reserve(n - k 1); int head 0, tail 0; // [head, tail) 存放下标 for (int i 0; i n; i) { while (tail head nums[q[tail - 1]] nums[i]) { --tail; } q[tail] i; if (q[head] i - k) { head; } if (i k - 1) { res.push_back(nums[q[head]]); } } return res; }这里有个很容易写错的地方弹出队尾时是--tail不是tail--。因为tail指向的永远是下一个空位最后一个有效元素是q[tail - 1]。如果你写tail--再访问q[tail]也可以但代码可读性会差很多。手写队列还有一个好处内存更连续访问速度通常会比deque快一点尤其在数据量特别大的时候体感更明显。3.3 动图太麻烦我们用表格手推一遍完整流程光看代码还不够建议跟着表格手推一次。下面用nums [1,3,-1,-3,5,3,6,7]k 3模拟。inums[i]入队前队列入队后队列过期检查后队列最终最大值01空[1:0][1:0]-13[1:0]弹出0[3:1][3:1]-2-1[3:1][3:1,-1:2][3:1,-1:2]33-3[3:1,-1:2][3:1,-1:2,-3:3][3:1,-1:2,-3:3]345[3:1,-1:2,-3:3]从队尾连续弹出3、-1、-3入队[5:4][5:4]553[5:4][5:4,3:5][5:4,3:5]566[5:4,3:5]弹出3、5入队[6:6][6:6]677[6:6]弹出6入队[7:7][7:7]7队列里我写成“值:下标”的形式。你会看到当一个大元素5出现时它会把前面所有小于它的值全部清掉这是整个算法最核心的淘汰逻辑。最终输出[3,3,5,5,6,7]和题目示例一致。3.4 优先队列与 multiset 的保底写法如果面试时一时想不起单调队列优先队列是很好的保底方案。思路是维护一个大根堆堆里存(值, 下标)二元组。堆顶一定是当前窗口某个元素但如果它已经过期就不断弹出直到堆顶是窗口内的元素。vectorint maxSlidingWindow(vectorint nums, int k) { priority_queuepairint, int pq; // 默认按 first 降序再按 second 降序 vectorint res; for (int i 0; i nums.size(); i) { pq.push({nums[i], i}); if (i k - 1) { while (pq.top().second i - k) { pq.pop(); } res.push_back(pq.top().first); } } return res; }这个写法简单但复杂度是O(n log n)。堆里可能堆积大量过期元素每次查询前都需要懒删除。数据量一大会比单调队列慢不少但好在不容易写错。multiset的版本也类似维护窗口内所有元素每次取*rbegin()是最大值。它更适合面试时作为“既然你提到了多种解法”的补充答案。4. 进阶延伸不同解法的取舍与优化空间4.1 优先队列为什么慢却常用优先队列慢在每次插入都要O(log n)删除过期元素也是均摊O(log n)。但它确实是最容易想到的解法而且代码量少不容易出现下标边界错误。很多线上编程题只要求结果正确用大根堆照样能过测试点。不过如果面试官想要的是O(n)你只答出大根堆面试官往往会追问一句“能不能优化到线性”这时候你再把单调队列讲出来才算完整。用优先队列还有一个细节priority_queuepairint,int默认按first降序如果值相同再按second降序。也就是说同值的元素下标更大的排在前面。这其实很友好因为下标更大意味着寿命更长。不过即便堆顶是新元素堆里仍然可能残留旧元素所以每次取结果前都必须循环弹出过期的堆顶。4.2 multiset 最容易踩的坑erase 到底删了谁multiset解法非常直观但有一个细节坑过我删除元素时必须用erase(find(x))不能直接写erase(x)。因为multiset允许多个相同值erase(x)会把所有等于x的元素全部删掉而窗口滑动每次只需要删除一个元素。multisetint s; for (int i 0; i nums.size(); i) { s.insert(nums[i]); if (i k) { auto it s.find(nums[i - k]); if (it ! s.end()) s.erase(it); } if (i k - 1) { res.push_back(*s.rbegin()); } }这里if (i k)的时机对应的是当前刚加入了nums[i]窗口右边界在i如果i k窗口左边界是i - k 1所以需要移出nums[i - k]。很多人在这一步写错成if (i k - 1)结果删除的是还没离开窗口的元素答案自然就错了。multiset写法好在不用处理下标缺点同样明显常数大复杂度是O(n log k)而且删除一个元素要配一个find代码容易显得啰嗦。4.3 分块预处理另一种 O(n) 的思路既然说到了O(n)还有一种不依赖队列的预处理做法用分块思想也能解。思路是把数组按大小为k切块预处理两个数组left[i]从当前块的左边界到下标i的最大值。right[i]从下标i到当前块的右边界最大值。对任意窗口[L, R]其中R L k - 1答案是max(right[L], left[R])。right[L]覆盖了从L到它所在块末尾这一段left[R]覆盖了从它所在块开头到R这一段两者合在一起正好覆盖了完整窗口。代码大概是vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint left(n), right(n), res; left[0] nums[0]; for (int i 1; i n; i) { left[i] (i % k 0) ? nums[i] : max(left[i - 1], nums[i]); } right[n - 1] nums[n - 1]; for (int i n - 2; i 0; --i) { right[i] (i % k k - 1) ? nums[i] : max(right[i 1], nums[i]); } res.reserve(n - k 1); for (int i 0; i k n; i) { res.push_back(max(right[i], left[i k - 1])); } return res; }这种做法的好处是思路直白坏处是要多开两个数组。它在比赛里偶尔能用上比如 POJ 2823 那道经典题就有很多人用单调队列或这招分块写。面试时如果能说出两种O(n)解法会显得你对数据结构理解比较全面。5. 常见问题与排查技巧实录5.1 结果数量不对先检查窗口边界最常见的报错是答案数组长度少了或者多了。滑动窗口第一段的下标范围是[0, k-1]所以记录答案的条件必须是i k - 1。我见过有人写成i k - 1也有人写成i k这两种都会漏掉第一个窗口的结果。如果你发现答案长度是n - k而不是n - k 1十有八九是这里的问题。还有个容易忽略的点当k 1时每个元素自身就是窗口最大值结果应该等于原数组。当k n时整个数组只有一个窗口结果长度是 1。这两个极端用例可以用来快速验证代码的边界处理是否正确。5.2 下标为什么必须存一个容易翻车的细节我之前看到有人把deque里的元素改成pairint, int存(值, 下标)这样也解决了过期判断问题。但更简洁的写法是只存下标真正需要值的时候再通过nums[q.front()]取。别小看这个选择它直接影响后面队尾淘汰判断的代码可读性。如果你存的是pair那判断条件会变成q.back().first nums[i]而存下标就是nums[q.back()] nums[i]后者直观得多。还有一点队首过期判断必须放在记录答案之前。逻辑顺序不对的话可能你记录的是一个已经不在窗口里的旧最大值。三步顺序建议固定成先弹出队尾、再入队、再查队首过期最后记录答案。写顺手了就不容易错。5.3 性能不够时手写队列怎么调用deque提交后被卡常数先把deque换成数组模拟队列一般能快不少。开一个vectorint大小为n用head和tail维护区间这是我在 POJ 上最常用的写法。另外注意res的reserve提前扩容也能省下很多次realloc。还有一个容易被忽视的小细节deque的.size()返回的是无符号类型nums.size()也是无符号。如果你在代码里写nums.size() - k而k是int会发生隐式类型转换有可能得到一个巨大的无符号数。建议先int n nums.size();后面都用n省得类型搞出莫名其妙的 bug。5.4 vscode 里 C 头文件报红及 IntelliSense 修复记录刷题时用的最多的环境可能不是 OJ 网站而是本地 vscode。我经常遇到#include deque下面出现红色波浪线但用终端编译却完全正常。这不是代码问题而是 IntelliSense 没找到头文件。一个非常常见的解决路径是按下CtrlShiftP输入C/C: Edit Configurations (JSON)打开.vscode/c_cpp_properties.json检查includePath是否包含了你的编译器自带头文件目录。比如用 MinGW 就找到 MinGW 安装目录下的include文件夹用 MSVC 就找 VS 安装目录下的 MSVC include 文件夹。同时把cppStandard: c17写进去。有些旧版本的 vscode 默认标准可能是 C98看到auto、emplace_back这类新特性就报红。改完后如果还不行执行一下C/C: Reset IntelliSense Database或者重新打开窗口。还有一点是C_Cpp.intelliSenseEngine设置默认值是default如果被改成了disabled那么所有智能提示和红色波浪线都会失效。5.5 自测用例清单刷题人自己的回归测试提交之前我习惯先在本地跑几个边界用例比直接交上去试错省时间。推荐准备这样一组测试nums [1,3,-1,-3,5,3,6,7]k 3预期[3,3,5,5,6,7]。nums [1]k 1预期[1]。nums [1,2,3,4,5]k 2预期[2,3,4,5]单调递增队里永远只有一个元素。nums [5,4,3,2,1]k 2预期[5,4,3,2]单调递减队里会有两个元素。nums [2,2,2,2,2]k 3预期[2,2,2]测试相等元素的下标更新。这组用例写完基本能覆盖所有边界分支空数组和k0一般不出现但如果你写在通用工具里最好也加上判空。多准备几组自测数据既是验证代码的保险也是加深理解的好方法。我个人在实际操作中的体会是这道题值得从暴力到单调队列、再从单调队列到手写队列分三遍各写一遍。第一遍感受暴力为什么慢第二遍理解单调队列为什么快第三遍则是在手写队列的过程中真正吃透双端操作的前后顺序。等你刷到 POJ 2823 或者类似的滑动窗口题目时这套模板直接套就能用几乎不用改。最后再分享一个小技巧每次做一个滑动窗口的题我都会把“过期判断”写在记录答案的前一行形成条件反射。你要是也容易忘就多敲几遍让这个顺序变成肌肉记忆。vscode 里如果头文件再报红先检查 IntelliSense 配置别让它影响刷题心情。