第一次做 LeetCode 1984 这道题时我盯着从数组中选出 k 个学生的分数使最高分和最低分的差值最小这句话看了很久。题目很短短到连个像样的背景故事都没有但恰恰是这种朴素题最容易让人踩进枚举所有组合的坑里。如果 n 只有 20你当然可以暴力但题目给到 1000 个分数时组合数 C(1000, k) 立刻变成天文数字暴力枚举必死无疑。后来我想明白一件事这道题表面考的是选数实际上考的是排序 固定长度滑动窗口。标题里把滑动窗口加了类似两个字是因为它和普通的双指针滑动窗口不完全一样——这里窗口长度固定为 k左右指针同步右移没有因条件收缩左边界的过程。但它分享同一个核心思想通过排序把杂乱的数据变成有序结构然后用一段连续区间去覆盖需要的答案。这篇文章把我完整的推导过程、三种语言的实现、容易翻车的边界细节以及从这道题能延展出去的一串相关题目都写出来给正在刷数组题和滑动窗口专题的朋友做参考。1. 先说服自己为什么要排序为什么又能滑窗1.1 暴力枚举劝退组合数增长太快先看题目本身给定一个整数数组nums和一个整数k要求选出任意k个学生的分数使得这k个分数中最大值与最小值的差尽可能小返回这个最小差值。很多人的第一反应是枚举所有组合从 n 个数里选出 k 个计算每组最大最小值的差取最小。这在 k2、n1000 的时候其实还能勉强跑完因为大概要枚举 50 万对但如果 k500、n1000组合数 C(1000, 500) 的数量级是 10 的 299 次方就算每秒钟能算 1 亿种组合也要算到宇宙热寂。所以暴力这条路从一开始就不通。那能不能用排序后取相邻 k 个数代替呢我第一次看到这个解法时也很怀疑凭什么最优解一定落在排序后连续的 k 个元素上万一最优解在排序后的数组里是跳着选的呢1.2 排序之后的关键性质最优解一定在连续区间上这个性质是可以严格证明的而且证明过程不难。先把数组升序排序得到a[0] a[1] ... a[n-1]。假设你选出了任意 k 个数它们在排序后数组中的下标是p1 p2 ... pk那么这组数的分数差是a[pk] - a[p1]。现在看一种特殊情况如果pk - p1 k - 1说明从p1到pk之间隔了不止 k 个位置中间至少有一个下标x不在你选的集合里。既然a[x]在a[p1]和a[pk]之间那把集合中离a[p1]或a[pk]较远的某个数换成a[x]最大最小值都不会变得更糟甚至可能变得更小。反复执行这个替换最终一定能得到一个连续区间[i, i k - 1]而且它的分数差不会比最初那组数更大。用人话说你要找的 k 个数本质上是在数轴上抱团最紧的一群点而排序后的数组恰好把所有点从左到右排好了最抱团的 k 个点必然是相邻的。这个结论成立的根本原因是分数差只取决于最大值和最小值选中的中间值不会对结果造成任何影响所以我们完全可以把注意力集中在区间跨度上。1.3 类似滑动窗口到底类似在哪经典的滑动窗口通常长这样右指针不断右移扩展窗口当窗口内不满足某个条件时左指针右移收缩窗口窗口长度是动态变化的。最典型的例子是最长无重复子串右指针每次加一个字符如果出现重复就挪左指针直到不重复为止窗口长度随字符出现情况不断改变。1984 这题不同窗口长度固定为k从下标0开始窗口覆盖[0, k-1]计算a[k-1] - a[0]然后窗口整体右移一位覆盖[1, k]计算a[k] - a[1]如此反复直到窗口右边界到达数组末尾。整个过程没有任何收缩动作更像一个长度为 k 的标尺在排好序的数组上从左往右滑动。所以标题里说类似滑动窗口非常准确思想是滑窗但实现上比经典滑窗简单得多本质是固定宽度窗口扫描或双指针同向平移。2. 题解实现三种语言版本与窗口移动细节2.1 Python 实现与代码注释class Solution: def minimumDifference(self, nums: List[int], k: int) - int: nums.sort() ans float(inf) n len(nums) # 窗口起点 i 的取值范围是 0 到 n-k # 窗口终点是 i k - 1必须小于 n for i in range(n - k 1): # 排序后窗口内最大值一定在右端最小值一定在左端 cur nums[i k - 1] - nums[i] if cur ans: ans cur return ans代码就这么短。核心只有三件事排序、定义窗口起点范围、用右端减左端更新答案。i的范围是range(n - k 1)我见过不少人在这一步写成range(n)结果nums[i k - 1]在数组末尾直接越界报错。这个边界必须想清楚窗口起点最多能走到下标n-k此时窗口终点是n-1刚好覆盖最后一个元素。另一个实现细节是ans的初始值。用float(inf)是最省事的也可以用nums[-1] - nums[0]作为初始上界因为任意 k 个数的差值都不可能超过整个数组的极差。两种写法都行但千万不要把ans初始化为0后面我会专门讲我因为这个犯过的错。2.2 C 实现与边界说明class Solution { public: int minimumDifference(vectorint nums, int k) { sort(nums.begin(), nums.end()); int ans INT_MAX; int n nums.size(); for (int i 0; i k - 1 n; i) { // 窗口终点下标是 i k - 1 ans min(ans, nums[i k - 1] - nums[i]); } return ans; } };C 版本基本上就是把 Python 翻译过来唯一要注意的是INT_MAX作为初始值。nums[i k - 1] - nums[i]不会超过int范围因为题目里的分数本身就在合理范围内即使考虑负数情况差值也不会溢出int直接用min更新即可。i k - 1 n这个循环条件比i n - k 1更直观也更不容易写错。我推荐使用前者因为它直接对应窗口终点必须在数组内这个约束。2.3 为什么推荐直接索引而不是切片取窗口有些同学会写出这样的版本for i in range(n - k 1): window nums[i:ik] ans min(ans, max(window) - min(window))这个写法在功能上是对的但在性能上是灾难。nums[i:ik]每次都会生成一个新的列表循环一轮下来总共要复制(n-k1)*k个元素时间和空间开销都变成 O(nk)。虽然题目数据 n 只有 1000 时看不出差别但一旦 n 到 10 万这个写法会慢到让人怀疑人生。正确做法是直接用下标访问nums[i]和nums[ik-1]。因为排序之后窗口内的最大值一定在右端点最小值一定在左端点根本不需要再调用max和min从头扫描一遍窗口。这是这道题能保持 O(n) 扫描的关键也是很多人没意识到的地方滑窗配合有序数组每次更新答案只要 O(1) 时间给算法省掉了整整一个因子 k。3. 复杂度、数据范围与易错点复盘3.1 复杂度拆解排序是绝对瓶颈整个算法分成两步排序和窗口扫描。排序O(n log n)Python 的list.sort()用的是 Timsort最好的情况是 O(n)最坏是 O(n log n)C 的std::sort用的是内省排序平均和最坏都是O(n log n)。窗口扫描O(n - k 1)每个窗口只要 O(1) 时间计算差值整体就是O(n)。空间复杂度取决于排序的实现。Python 的 Timsort 需要 O(n) 的临时空间C 的内省排序是原地排序O(log n)可以近似看成O(1)。所以这道题的时间瓶颈完全在排序上窗口扫描那部分几乎不花时间。这也是为什么不管数据长什么样O(n log n)就是这个题的复杂度下限——除非你另辟蹊径比如用计数排序把排序阶段优化到 O(nv)后面我会在延伸章节展开。3.2 边界条件逐一过一遍这道题有几个边界条件我很建议你在提交前逐个检查k 1只选一个学生最大值等于最小值答案恒为0。用上面的代码天然返回0不需要特判。我见过有人专门为 k1 写 if 分支属实多余。k n必须选所有学生答案就是整个数组的极差。窗口起点唯一循环只跑一次代码也能正确覆盖。数组中有重复分数排序后重复值相邻只要某个固定窗口恰好覆盖了一段重复区域差值可能为0答案可以提前返回。但提前返回只是微优化不会改变复杂度。空数组题目保证nums至少有一个元素k也保证1 k n所以理论上不需要防御空数组。但如果你把这题改造成工具函数加一句if not nums: return 0之类的防御性判断也完全合理。3.3 我真实翻车过的两个小细节第一件事是ans初始值。我最早写的版本把ans初始化成0心想最小差值再小也就是 0用 0 起步没问题。结果窗口扫描时cur永远不小于 0min(0, cur)永远返回 0答案全部错成 0。样例恰好是 k1 的情况0 正好正确于是样例过了、提交挂了。这种样例全过、提交全挂的问题最坑排查了半天才发现是初始值选错。后来我给自己立了个规矩求最小值的变量初始值要么是float(inf)C 用INT_MAX要么是数组内一个足够大的合法值用 0 这种值做初想必死无疑。第二件事是求最小差值时写成max(window) - min(window)。我前面提到了切片会复制数组但更本质的问题是在有序数组里窗口内的极值就是两个端点不需要再调用线性扫描的max和min。这一步做错扫描阶段就从 O(n) 退化成了 O(nk)虽然小数据看不出来但面试官一眼就能看出你对有序结构带来 O(1) 更新这个点理解得不够透。4. 从1984扩散出去一道题解锁一串题目4.1 固定长度窗口的经典变形1984 属于排序 固定长度窗口这个套路里最简单的一种窗口内只需要极差而且窗口长度固定所以标尺式扫描就够了。这个套路还能延展出很多变体LeetCode 643 子数组最大平均数 I固定长度为 k 的窗口求和然后除以 k滑动时加右端减左端O(n) 完成。它和 1984 的区别只在于窗口内的聚合函数是求和而不是求极差。LeetCode 1052 爱生气的书店老板同样是固定窗口只是窗口内要结合另一个数组做条件判断滑窗的骨架完全一样。LeetCode 220 存在重复元素 III要求判断是否存在两个数的差不超过 t 且下标差不超过 k。这个题就要借助有序集合或桶排序维持窗口内的有序状态比 1984 难一档但它的窗口思想仍然是核心。刷这类题的关键不是背代码而是识别出三个东西窗口长度是否固定、窗口内的聚合函数是什么、数据是否需要在窗口内保持有序状态。1984 把有序状态前置到了排序阶段之后窗口就只剩减法和比较两个动作了。4.2 值域很小时的进阶优化计数排序双指针1984 的 n 只有 1000O(n log n)随便跑。但如果数据规模变成n 10^6而分数值域很小比如分数是 0 到 1000 之间的整数排序可以改用计数排序把复杂度压到O(n v)其中 v 是值域范围。思路是先统计每个分数出现次数然后按分数从小到大扫描把出现次数累加并维护长度为 k 的人数窗口窗口内左端分数和右端分数的差就是当前候选答案。这个做法本质上是把排序数组上的固定窗口搬到了计数数组上的双指针扫描当值域远小于元素个数时效果非常明显。别急着说这是过度优化这个思路在真实业务里很常见。比如分析一批用户评分评分范围 1 到 5用户量几百万排序一百万条评分完全没必要直接数每个分段的人数再滑窗即可。算法题做到最后会发现很多优化思路都能迁移到实际系统里。4.3 面试官追问如果 k 不固定你怎么做1984 是给定一个固定的 k如果改成查询若干次不同的 k每次都返回最小差值呢排序仍然要做但每次查询都重新滑一遍窗口就是 O(qn)q 是查询次数。当 q 很大时需要预处理一些信息来加速回答任意长度的窗口极差最小值。常见思路是维护一个值域上的结构比如分段统计或者对每个起点二分查找能让差值不超过某个阈值的最大窗口长度配合前缀结构做快速判断。这个问题在面试里的价值不在于真的要做多复杂而在于考察你能不能说出排序一次、多次利用的思路而不是每来一个 k 就重新排序。很多经典题目都是靠这道题的变体当成面试递进题来用前面答出基础版后面答出扩展版评价会高不少。5. 刷题与面试时怎么把这个解法讲漂亮5.1 讲题顺序比代码更值钱我见过很多人在面试里一上来就写代码排序完直接滑窗代码三分钟写完但面试官问为什么排序后只需要检查连续 k 个元素就卡住了。这道题考察的重点恰恰是这个为什么而不是排序和循环本身。我自己的讲题顺序是先说暴力枚举组合 C(n,k)n 稍大就不可行所以需要利用差值只取决于最大值和最小值的性质。再讲排序的动机排序后所有候选区间被压缩到了 O(n) 个因为最优解中的 k 个数在排序后必然相邻否则可以把中间未选的数换进来差值不会变大。最后讲窗口扫描固定长度为 k右端点减左端点一遍扫描取最小值。如果面试官追问复杂度排序 O(n log n)扫描 O(n)空间看排序实现。这个顺序等于把猜结论变成给证明面试官一听就知道你不是背题而是真的理解了解法背后的结构。5.2 语言差异里的隐藏坑这道题虽然简单但不同语言的排序实现各有各的坑。Python 的list.sort()是原地排序、稳定排序不会出问题C 的std::sort对基本类型直接用比较也没问题但如果你用 JavaScript 刷题Array.prototype.sort()默认按字符串字典序排序不传比较函数时[10, 9, 100]会被排成[10, 100, 9]结果完全错乱。所以 JS 版必须写成nums.sort((a, b) a - b)。Java 刷题时如果用了Arrays.sort对基本类型数组排序没问题但如果把Integer[]和int[]混着用初始化的方式不对会多出一堆装箱开销写代码时留意一下类型即可。这些语言细节在题解里经常被忽略但恰恰是实战中报错率最高的地方。尤其写惯了 Python 的人切换到 JS 时特别容易在排序这一步翻车。5.3 我的个人体会与一个小技巧按我刷题一年的经验像 1984 这种简单不难但容易想歪的题最大的价值是建立条件反射看到选 k 个元素使极差最小/最大先想排序再看连续区间是否覆盖所有最优候选。这个条件反射在 LeetCode 上能直接套到至少一二十道题里在真实数据分析场景中也非常实用——比如从一堆价格里选 k 个商品让囤货价差最小本质就是同一道题。最后分享一个小技巧适合写题解或做笔记这类题的代码骨架可以记成排序定序窗口平移端点更新。排序解决了数据的无序问题窗口把组合枚举变成线性扫描端点更新利用有序性把窗口内的统计降到 O(1)。以后遇到任何固定窗口 区间极值的题目先想想能不能通过排序让窗口内天然有序能的话代码就直接照着这个骨架写。这个思维模型比记住这一题的代码值钱多了。