第170场双周赛做Q2的时候我盯着“3751. 范围内总波动值 I”这个标题愣了一下——这题名看起来像是要把人绕晕实际上题目逻辑一旦拆开就是一道非常经典的“滑动窗口最值求和”。比赛结束后我复盘了一下发现这道题卡住不少人的点不在算法本身而在三处一是没看透数据规模一定要你上O(n)做法二是单调队列的入队淘汰规则没有真正理解导致写错符号三是边界和取模处理得不干净。这篇就按我自己的复盘思路把这道题从暴力到正解到对拍验证讲透适合正在备战周赛、面试前刷单调队列、以及想搞懂“窗口滑动时最值怎么增量维护”的读者。1. 先拆题波动值总和到底在求什么1.1 数学化把“每个窗口的max-min”写成求和公式题意说白了就是给你一个数组nums和一个固定窗口长度k每个长度为k的连续子数组都算一次“最大值减最小值”然后把这些差值全部加起来最后对10^97取模。用公式写就是其中n是数组长度总共有n-k1个窗口。举个例子nums [1, 3, -1, -3, 5, 3, 6, 7]k 3窗口[1, 3, -1]max3min-1波动值4窗口[3, -1, -3]max3min-3波动值6窗口[-1, -3, 5]max5min-3波动值8窗口[-3, 5, 3]max5min-3波动值8窗口[5, 3, 6]max6min3波动值3窗口[3, 6, 7]max7min3波动值4总和是46883433。题名里的“范围内”指的就是这个固定半径的滑窗“总波动值”就是这些差值的累积。核心难点只有一个每个窗口都要拿最大值和最小值怎么拿得又快又准。1.2 数据规模暗示了算法级别如果n只有几千直接跑O(n·k)暴力一点问题都没有。但这类双周赛Q2通常会把n拉到10^5甚至10^6。假如n100000、k50000暴力就是50000 * 50001 ≈ 2.5e9次操作——这个量级在C里都奔着好几秒去了换到Python基本必超时。所以看到“范围内 固定k 求和”这个组合第一反应就应该是这题要O(n)。这意味着每个元素最多被常数次数的处理不能再像暴力那样每个窗口独立扫描。这是题目给我们的第一层暗示。第二层暗示是既然要维护滑动窗口的最值而且窗口只在右端加、左端删那么一个双端队列结构几乎就是为这个场景量身定做的。1.3 先写一个O(n·k)的暴力版拿分、对拍两不误正解归正解我写题有个习惯先花两分钟写一版暴力哪怕它过不了全部数据。它的价值有两个——小数据能拿分对拍时做“裁判”。long long brute(vectorint nums, int k) { int n nums.size(); long long res 0; for (int i 0; i k n; i) { int mx INT_MIN, mn INT_MAX; for (int j i; j i k; j) { mx max(mx, nums[j]); mn min(mn, nums[j]); } res mx - mn; } return res; }这代码没有任何技巧纯粹枚举所有窗口再扫一遍。虽然是O(n·k)但它正确性一目了然。后面我写单调队列版本时就用它当“标准答案”随机生成数据对比两个结果。没有这一步正解写歪了你自己都很难发现。2. 单调队列为什么滑动窗口的最值适合用双端队列维护2.1 从窗口滑动看增量维护的动机暴力慢就慢在每个窗口“重新扫描”。但仔细想一下窗口每次只变化两个位置右端进来一个新元素左端出去一个老元素。中间那k-1个元素根本没变。如果我们要维护“当前窗口内最大值是多少”能不能不用重新扫而是在上一次答案的基础上增量更新增量更新的难点在于出去一个元素可能正好是最大值那新的最大值是谁你只靠维护一个“当前最大值”是回答不了这个问题的因为你要知道第二大的元素是谁甚至第三大、第四大……这就是为什么我们需要一个有序的候选队列。队列里存的不是所有元素而是“有资格成为未来窗口最大值”的候选者。2.2 入队淘汰规则新元素如何“挤掉”老元素维护最大值的单调队列核心规则只有一条入队前把队尾所有小于等于新元素的元素全部弹出再把新元素从队尾压入。也就是说队列里从队头到队尾元素值是严格递减的队头永远是当前窗口里最大的候选。这个规则的直觉可以用“插队排队”来理解想象窗口里的元素是一排排队的人每个人的“身高”就是元素值你需要知道队里最高的人是谁。新来一个人如果他比排在他前面的人都高那前面那些人在“找最高的人”这件事上就再也没有用途了因为这个人又高又更晚走。与其留着这些人占地方不如全部清掉直接让新人站到最前面。看一个具体演变nums [1, 3, -1, -3]维护最大值队列元素入队前队列操作入队后队列1空直接入队[1]3[1]3 1弹出1[3]-1[3]-1 3直接入队[3, -1]-3[3, -1]-3 -1直接入队[3, -1, -3]注意当3进来时1被弹出。为什么因为3下标更新、值更大只要有3在窗口里最大值轮不到1而3比1晚离开窗口。所以1永远失去了做最大值的机会淘汰它没有任何损失。2.3 为什么选择deque而不是优先队列一个关键的不变量你可能会问求滑动窗口最大值用优先队列大根堆加上“下标过期再删除”不也能实现吗能但有两个问题。第一是复杂度。优先队列的插入和删除是O(log k)总复杂度O(n log k)。在n1e5时差别不大但当n到1e6、时限卡在1秒的题目里log因子会让代码变得很危险。单调队列每个元素最多入队一次、出队一次总体O(n)这是量级的差距。第二是“过期清理”的干脆程度。优先队列的堆顶可能是当前最大值但如果被窗口移出去的元素不是最大值它就会像垃圾一样留在堆里堆顶长期被一堆过期元素霸占每次取最值时还要反复检查下标、弹掉过期堆顶。而单调队列有一个非常漂亮的不变量队头元素一定是窗口里最老的候选者。因为队头在队列里待得最久窗口左端滑出元素时如果滑出的元素是队头直接pop_front就行如果滑出的不是队头说明它不是候选者本来就被淘汰了也不用管。这一下把“过期删除”变成了O(1)的队头判断。队列里存什么存下标不存值。因为下标天然单调递增判断过期直接front() i - k即可同时还能通过下标查回原数组的值。3. 双队列同步滑窗完整实现与顺序玄机3.1 最大值和最小值是“镜像对称”的最大值队列是递减的最小值队列就是递增的队头永远是最小值。规则完全对称维护最小值的队列入队前把队尾所有大于等于新元素的元素弹出再让新元素入队。这里有个特别容易翻车的细节最大值队列用弹出最小值队列用弹出。为什么相等值也要弹拿最大值队列来说如果新元素和队尾元素值相同新元素下标更大意味着它在窗口里待得更久。既然值一样留着旧的不如换新的这样队列里更“年轻”过期判断更干净。反过来如果相等时不弹旧元素也不会算错但队列里会堆一些“永远用不上”的旧候选极端情况下队列长度很久不降白白增加空间和判断。3.2 清理过期、入队、统计三个操作的正确顺序写单调队列题我见过最多的错误就是顺序问题。标准流程是枚举右端点i从0到n-1每个位置做三件事先清理两个队列队头的过期下标条件front() i - k再按淘汰规则把nums[i]插入两个队列当i k-1也就是窗口[i-k1, i]完整时用两个队头算max - min并累加这个顺序可以理解为“先拆旧、再迎新、最后统计”。如果先入队再清理过期行不行绝大部分情况也行只要你保证统计前队头是干净的。但我还是建议统一用“先清理再入队”因为你入队时如果队里还有一堆过期元素你淘汰队尾时比较的nums[back]可能是过期元素的值逻辑上虽然不会错但会让人多一层不必要的思考。还有一个更隐蔽的坑入队和统计循环的条件。如果你枚举的是窗口左端点而不是右端点很容易把i k-1写成ik n然后越界访问。我最开始写这道题时统一用右端点代码对称性更好不容易出边界错。3.3 完整代码与逐行走读class Solution { public: int sumOfSlidingWindowValue(vectorint nums, int k) { const int MOD 1e9 7; int n nums.size(); dequeint maxQ, minQ; long long ans 0; for (int i 0; i n; i) { while (!maxQ.empty() maxQ.front() i - k) maxQ.pop_front(); while (!minQ.empty() minQ.front() i - k) minQ.pop_front(); while (!maxQ.empty() nums[maxQ.back()] nums[i]) maxQ.pop_back(); maxQ.push_back(i); while (!minQ.empty() nums[minQ.back()] nums[i]) minQ.pop_back(); minQ.push_back(i); if (i k - 1) { ans (ans nums[maxQ.front()] - nums[minQ.front()]) % MOD; } } return (int)ans; } };有人会问maxQ和minQ里存一样的内容吗不是的它们是两个完全独立的队列。maxQ的队头是窗口最大值候选minQ的队头是窗口最小值候选中间内容各不相同互不影响。空间上每个队列最多存k个下标实际上通常远小于k因为淘汰规则会让队列保持精简。我用一个具体例子完整跑一遍两个队列加深理解。设nums [2, 4, 1, 3]k 2i0maxQ存[0]minQ存[0]不满一个窗口i1maxQ队头0未过期0 -1不满足保留入队前nums[maxQ.back()]2 4弹出0maxQ变成[1]。minQ里2 4不成立所以minQ保持[0,1]。此时窗口[0,1]max4min2差2i2maxQ队头1过期吗1 2-20不成立不过期。入队1nums[1]4 nums[2]1不成立所以maxQ变成[1,2]。minQnums[1]4 1弹出1nums[0]2 1弹出0minQ变成[2]。窗口[1,2]max4min1差3i3maxQ队头1过期吗1 3-21成立弹出。maxQ变成[2]。入队3nums[2]1 nums[3]3弹出2maxQ变成[3]。minQ队头2过期吗2 1不成立。入队3nums[2]1 nums[3]3不成立minQ变成[2,3]。窗口[2,3]max3min1差2总和2327。你对照代码看这个过程会发现所谓队列维护其实是把每个元素“有资格当下一个最值”的时机都盘算清楚了。这也是为什么它能O(n)每个元素最多被队列push一次、pop一次没有多余操作。4. 边界条件、取模与暴力对拍从能跑到能过4.1 边界用例清单写完代码第一件事不是提交而是测边界。这道题有几个典型边界用例期望结果原因k10每个窗口只有一个元素max-min0knmax(nums)-min(nums)全数组只有一个窗口数组全相等0任何窗口 maxmin数组严格递增固定规律最小值恒为窗口第一个元素最大值恒为最后一个可手算验证数组严格递减固定规律与递增对称含负数正常求和波动值本身与正负无关但累加时避免用无符号类型我测k1时会重点看队列逻辑i0时还没到ik-1不统计i1时队头下标0 i-k 0正好被弹出窗口[1,1]的队头是1maxmin差为0。这个清理条件front() i-k在k1时每个元素只在窗口里活一步验证下来是精确的不多删不少删。4.2 结果很大何时取模、用什么类型累加题目说答案对10^97取模但累加过程中要不要每次都取模先说数学如果nums[i]绝对值最大到10^9那么单个窗口的max-min最大也是10^9量级窗口数最多n-k1 ≤ 10^5总和不取模大约是10^14量级。这个数远小于long long的上限9.22e18所以理论上可以最后一次性取模。但我实际写比赛代码时会选择每一轮都取模。原因有两个第一取模操作本身只是%MOD现代CPU上代价微乎其微对1e5规模完全不构成性能压力第二如果题目在后续版本里修改了数据范围比如nums[i]改成10^18或者n改成10^7只在最后取模的写法就容易爆long long。提前取模的代码多一行但心理负担小很多。还有一种写法是ans (ans (nums[maxQ.front()] - nums[minQ.front()]) % MOD MOD) % MOD;nums[maxQ.front()] - nums[minQ.front()]本身一定是非负的因为max至少等于min所以不需要MOD修正。但如果哪一天题目改成维护“距离”或者“绝对值”减法出现负数就需要这样写。现在这道题干净地一行取模就够。4.3 暴力对拍随机数据验证的正确姿势我强烈建议把暴力函数和正解函数放在同一个测试程序里对拍。流程很简单随机生成n比如1到20之间、k1到n之间、以及n个随机整数分别跑solve(nums, k)和brute(nums, k)比较结果不一致就打印数据并中断一个典型的测试循环srand(20250420); for (int t 0; t 5000; t) { int n rand() % 20 1; int k rand() % n 1; vectorint a(n); for (auto x : a) x rand() % 41 - 20; // -20 到 20 long long r1 solve(a, k); long long r2 brute(a, k); if (r1 ! r2) { cout WA on test t \n; // 打印 n, k 和数组 return 0; } } cout all passed\n;数据规模小一点结果远小于MOD直接比较long long不会出现“答案超过MOD但正解取模后与暴力不等”的假失败。我实际对拍时曾经靠这个脚本抓到了一个符号错误min队列的被我复制成了导致相等值没有淘汰旧元素。小数据里结果碰巧全对但随机数据一多就现形了。没有对拍这种错交上去就是WA或TLE。4.4 实测表现n10^5时的时间与空间正解代码用双端队列存下标空间上两个队列最长各为k也就是最多存2k个int。在n1e5、k5e4时内存开销可以忽略不计。时间上我本地用-O2编译随机数据跑了大概不到10ms换到n1e6也就80ms上下。这个性能足够应对绝大多数周赛Q2了。顺带一提有人担心std::deque底层是分段连续存储会不会比vector慢。对于只做push_back/pop_back/pop_front的场景deque的常数非常稳定瓶颈不在数据结构而在输入输出。如果要极限压榨性能可以换成数组模拟的双端队列两个vectorint 头尾指针但通常没必要可读性差且容易引入越界。5. 从这道Q2延伸出去三个高频变形方向5.1 变形一不限制k求所有子数组的波动值总和题目名字带个“I”很自然会想到后面有没有“II”。最大的可能是扩展成给定数组求所有连续子数组长度任意的max-min总和。这题就不能用滑动窗口了因为子数组数量是O(n²)窗口思路直接失效。正确的打开方式是“贡献法”把总和拆成“所有子数组最大值之和”减去“所有子数组最小值之和”。每个元素能成为多少个子数组的最大值用单调栈找到左边第一个大于它的位置L右边第一个大于等于它的位置R那么以它作为最大值的子数组数量就是(i - L) * (R - i)。求最小值同理只是找的是小于/小于等于。这里的技巧在于一边取严格不等、另一边取非严格不等才能保证每个子数组的“最大值位置”唯一不重不漏。为什么提这个因为如果你看穿了Q1的单调队列其实你已经掌握了“维护候选者”的思维变形一的单调栈就是同一个思维的静态版本——队列是滑动窗口的动态淘汰栈是全局区间的边界划定。周赛里常把这两题放在前后场次不是没有原因的。5.2 变形二二维矩阵上的k×k滑窗最值如果你觉得一维滑窗太简单了面试官下一步就会把数组变成m×n的矩阵要求每个k×k子矩阵的max-min总和。做法就是二维单调队列分两步对每一行做一维单调队列得到横向每个长度为k的窗口的最大值形成一个m×(n-k1)的中间矩阵对中间矩阵的每一列再做一次一维单调队列得到纵向每个长度为k的窗口的最大值最终每个格子对应一个k×k子矩阵的最大值最小值同理最后逐格累加差值。复杂度是O(mn)空间O(mn)。这个套路在竞赛里叫“二维滑窗最值”很多矩阵相关的题目都建立在它上面。核心还是同一个单调队列只是把队列复用了两遍。5.3 变形三面试里的追问——优先队列为什么不行面试官考这道题时大概率会在你写出单调队列解法后追问优先队列能不能做如果我说能但更慢他就会继续问“慢在哪”。我一般会这么回答优先队列只能保证堆顶是最值但你不知道堆里哪些元素已经离开窗口。取最值时如果堆顶过期就得不断弹出而我们没法按需删除窗口里滑出去的那个“中间元素”所以堆里会积累垃圾。类的每一项操作都是O(log n)而单调队列每个元素进出O(1)。更重要的是单调队列的队列序列本身就是一个有序的候选链可以O(1)拿到最值不需要任何额外的堆调整。把这个问题想清楚比背十遍模板都有用。面试官想听的其实是你对“数据结构如何匹配问题增量过程”的理解而不是你背下来的while循环长什么样。我个人做完这道题的体会是单调队列这道坎跨过去之后很多题会突然变得通透。它本质上是一种“增量维护有序候选集合”的思维——先把窗口看成一条流动的生产线再想清楚每个元素在什么条件下会成为下一轮的主角什么时候可以功成身退。如果以后遇到看起来更唬人的“范围内XXX”先别慌动手拆一层说不定底下就是又一个滑动窗口。最后再分享一个我自己受益很多的小习惯别再新题上直接奔着AC去暴力版、正解版、对拍脚本一起上虽然多写几分钟但提交时那种“这个真能过”的确定感值回票价。