今天的每日一题是 LeetCode 1984——学生分数的最小差值。看到这个题号我第一反应是奥威尔的小说点进去才发现是一道标着 Easy 的数组题。但说实话别被难度标签骗了这道题把“排序”和“滑动窗口”这两个最高频的基础套路揉在了一起刷明白它比闷头做十道同类型变体更有价值。这篇文章我会从读题拆边界开始讲到排序后为什么敢用定长窗口、代码实现的细节坑位再顺手把这一类“最小极差”题型的延伸方向理一遍适合刚开始刷题、或者想把这个套路彻底吃透的朋友。1. 题意拆解题目究竟在问什么1.1 原题在问什么别把“任意选”看成“连续段”原题描述不长给定一个整数数组scores和一个整数k要求从数组中任意选择 k 个学生的分数计算这 k 个分数里最高分和最低分的差值最后让这个差值尽可能小返回最小可能差值。很多第一次做的人会惯性误读成“从数组中挑一段连续的、长度恰好为 k 的子数组计算这一段里的最大值减最小值”。这个误读相当致命因为题目说的是pick the scores of any k students重点在那个any上被选出来的人在原数组里可以不挨着。我举个能看出区别的例子。假设分数是[9, 4, 1, 7]k 2。如果你按“连续子数组”理解窗口[9,4]的差是 5[4,1]的差是 3[1,7]的差是 6最小值是 3。但如果允许任意选选7和9差是 2——而这两个数在原数组里的下标分别是 3 和 1根本不在一个连续窗口里。所以这道题正解答案是 2不是 3。我建议第一次做这题的朋友把这个例子手推一遍推完你对题意会非常清醒。这个误读也提醒我们一件事数组题里“连续子数组”和“任意子集”是两种完全不同的约束读题时第一件事就是分清这个。很多时候题目做错不是方法不对是问题理解偏了。1.2 恰好 k 个的边界情况k1 和 kn题目要求的是“恰好 k 个学生”不是“最多 k 个”也不是“至少 k 个”。这个“恰好”在边界上会引出两个值得提前想清楚的情况。第一k 1。你只能选一个人那最高分和最低分都是同一个分数差值必然是 0。这一点看起来简单但不少人写代码时会在窗口初始值上翻车——比如把答案初始值设成 0那无论滑窗扫出什么结果答案永远是 0或者不单独处理k1导致窗口只有一个元素时 diff 计算方式不对。其实用“初值设为最大整数”的写法k1的情况会被自然覆盖后面代码部分细说。第二k scores.length。没有任何选择的余地只能全选答案就是整组数据的最大值减最小值也就是排序后最后一个元素减第一个元素。这两种极端情况一旦想透代码的循环边界就不会写错了。另外分数数组可能是无序的也可能包含重复值。重复值不影响算法正确性但会让“最小差值是 0”的情况更容易触发。力扣原题里分数范围是 0 到 100但做算法题最好不要依赖这个假设——你的解法应该能处理任意整数数组哪怕分数是负数也一样工作。1.3 差值的语义只关心最大值与最小值还有一个容易跑偏的地方题目要计算的是“最高分减最低分”也就是max - min不是把选出的 k 个数排序后算相邻两项的差也不是算某种“总距离”。这句话背后的含义是中间那 k-2 个数选谁其实不影响最终差值只要它们别超过两端就行。我们真正关心的是选出来的 k 个数在数值轴上能不能“挤得足够近”。这个直觉非常重要因为后面“排序之后为什么可以只看连续窗口”的证明靠的就是这一点。把这三节读下来题意的所有边界都扫清了。接下来要考虑的是到底怎么把答案算出来才不会在组合数上爆炸。2. 从暴力枚举到排序滑窗正确性怎么想出来的2.1 暴力枚举的复杂度C(n,k) 有多可怕最直觉的做法当然是把所有“从 n 个分数里选 k 个”的方案都枚举一遍每组算一下 max 和 min取全局最小差值。我算给你看当n 1000、k 2时组合数是 C(1000,2)大约 50 万勉强还能接受可一旦k 5C(1000,5) 直接到了 8.2 万亿量级现代计算机也要跑很久。哪怕把规模缩小到n 100、k 50C(100,50) 也是一个天文数字。暴力枚举在绝大多数情况下是不可行的。那优化方向在哪注意差值只取决于选出的最大值和最小值中间的数不重要。既然中间不重要我们自然会想要让差值小选出来的数就应该在数值轴上“尽量靠近”。而“数值轴上的靠近”一旦落到有序数组里就是“下标上的靠近”——这正是排序的用武之地。2.2 为什么排序后极差一定出现在连续窗口里把scores从小到大排序得到有序数组nums。现在的问题变成从有序数组里选 k 个数让nums[最大值下标] - nums[最小值下标]最小。为什么这种情况下最优解一定落在“长度恰好为 k 的连续子数组”里这里有一个非常关键但又容易一笔带过的论证我展开说。假设全局最优解选出的 k 个数在排序数组里的最小下标是L最大下标是R。那么区间[L, R]内至少有 k 个数也就是R - L 1 k。这个区间内部任意取 k 个数极差都不会超过nums[R] - nums[L]而原最优解的极差正好是nums[R] - nums[L]最大值和最小值就落在两端万一最优解并没有选端点上的数那就是说选中的数对应的极差更小和“最优解取到了端点”矛盾实际上我们可以直接取那些真正被选中的数的范围和最小范围继续论证。换句话说任何“不连续”的选法都能在这个选法覆盖的区间里找到一个更紧密或者至少不差的选法。不断地把区间收紧到只包含 k 个数极差只会变小不会变大。所以全局最优解一定可以在“排序数组里所有长度为 k 的连续子数组”中找到。这个论点就是整道题正确性的基石。面试时如果能把这段话讲清楚比默默写出正确答案要加分得多。有一个更生活化的类比想象数值轴是一排座位你要找 k 个坐得最密的人。那最密的 k 个人在排好队的队伍里一定是相邻的——如果他们中间还隔着没被选的人把那些人换成中间的人只会让“最左和最右的距离”更小或不变。这就是“连续窗口”直觉的来源。2.3 定长窗口的滑动逻辑既然答案一定出现在长度为 k 的连续子数组里事情就简单了。排序后的数组长度为 n窗口左端点 i 从 0 走到n - k每个窗口的差值是diff nums[i k - 1] - nums[i]把所有 diff 取最小即可。这里需要注意窗口长度是固定的 k所以不需要像“无重复字符的最长子串”那样伸缩窗口只是一个纯粹的 for 循环加一次下标运算。这也是滑动窗口里最简单的一种形态——定长窗口。整体复杂度是排序 O(n log n) 加滑窗 O(n)合起来 O(n log n)空间上只有排序栈开销可以认为是 O(1) 额外空间如果忽略排序内部栈。这个复杂度在 n 达到 10 万级别时跑起来毫无压力。3. 代码落地Java 与 Python 实现的边界坑位3.1 Java 实现与细节注释先直接给 Java 版本我把关键行都写了注释。import java.util.Arrays; class Solution { public int minimumDifference(int[] nums, int k) { // 排序是前提没有排序就没有“连续窗口”这个结论 Arrays.sort(nums); int n nums.length; // 初始值用最大整数这样第一个窗口的差值一定能覆盖它 int ans Integer.MAX_VALUE; // 左端点最多走到 n-k再往右窗口就不完整了 for (int i 0; i k - 1 n; i) { // 窗口右端点下标是 i k - 1不是 i k ans Math.min(ans, nums[i k - 1] - nums[i]); } return ans; } }写这个代码时我最想强调的是循环终点。很多人会下意识写i n然后访问nums[i k - 1]时直接数组越界。正确写法是i k - 1 n等价于i n - k 1。把边界条件当作“右端点必须存在”来记比硬背公式靠谱。3.2 Python 实现的不同侧重Python 版本可以写得更简洁但简洁不等于可以忽略边界。class Solution: def minimumDifference(self, nums: List[int], k: int) - int: nums.sort() n len(nums) # 用正无穷做初值保证第一次比较必然更新 ans float(inf) # range 的终点是 n-k1这样 i 最大取到 n-k for i in range(n - k 1): diff nums[i k - 1] - nums[i] if diff ans: ans diff return ansPython 里range(n - k 1)这种写法天然规避了越界比 Java 的循环条件看着舒服一些。但对那些刚开始用 Python 刷题的人来说有一个隐蔽的问题nums.sort()会原地排序如果你后续还要用到原始顺序就会踩坑。这题只关心最终差值原地排序完全没问题但这种“把原数组改掉”的操作在很多题目里是有副作用的养成“是否需要复制数组”的习惯会少踩很多坑。另外有些朋友喜欢用列表推导式和min一行流class Solution: def minimumDifference(self, nums: List[int], k: int) - int: nums.sort() return min(nums[i k - 1] - nums[i] for i in range(len(nums) - k 1))这写法没问题也很快。不过我个人的建议是一行流适合比赛或事后复盘时炫技日常练习和团队协作里还是写成显式循环更好读。面试时写出一行流如果面试官不熟 Python可能还要你现场解释一遍得不偿失。3.3 最容易写错的三个点我把这道题常见的 bug 汇总成一个表方便对照自查。错误写法出错原因正确做法for (int i 0; i n; i)左端点走到 n-1 时i k - 1已经越界当 k 1循环条件用i k - 1 nnums[i k] - nums[i]右端点下标多算了 1最后一个窗口没被检查右端点是i k - 1不排序直接滑窗窗口内并不保证是数值上最接近的 k 个数必须先排序再滑窗ans初值设为 0答案永远被 0 覆盖可能提前返回错误值初值设为Integer.MAX_VALUE或float(inf)这表里的第一条和第二条是我在评论区见过的高频错误几乎每周都有新人踩一遍。其实这些坑都有同一个根源把一个 k 元素窗口的“最后一个元素下标”算错了。窗口起点是 i那么窗口内元素是nums[i], nums[i1], ..., nums[ik-1]右端点是ik-1不是ik。想清楚这一个公式至少三个坑同时消失。3.4 样例与性能把输出推一遍拿前面用过的例子完整手推一遍确保没有“代码会写但脑子里不落地”的感觉。scores [9, 4, 1, 7]k 2。排序后[1, 4, 7, 9]。窗口i0nums[1] - nums[0] 4 - 1 3窗口i1nums[2] - nums[1] 7 - 4 3窗口i2nums[3] - nums[2] 9 - 7 2答案取最小也就是 2。和前面任意选择的分析一致。性能上我也提一句这个解法在 n 为 10 万、k 任意时排序加上一次线性扫描总耗时通常只有几毫秒到十几毫秒力扣上跑这题的用时分布非常集中在前面。暴力解法在 n 稍微大一点时就不是“慢”的问题而是“根本算不完”。4. “最小极差选 k 个”的通用套路与延伸题4.1 从 1984 提炼出的解题模板刷题最有价值的产出不是做出这一道而是从这一道里长出一个可以复用的思维模型。1984 的模型可以提炼成三个特征词数组、恰好选 k 个、让最大值和最小值相关的东西尽可能小。只要题目同时包含这三个特征大概率可以这样走先排序用一个固定长度 k 的窗口或者双指针在有序数组上扫描对每个窗口计算题目要的指标维护全局最优值。排序的作用是把你对“数值相近”的直觉变成可计算的下标相邻关系。窗口的作用是把组合枚举从指数级坍缩成线性扫描。这个套路覆盖面极广从“选 k 个使极差最小”到“找到离 target 最近的 k 个数”再到“第 k 小的数对距离”本质都是同一棵树上长出来的枝叶。4.2 延伸题一找到 K 个最接近的元素LeetCode 658先看一个和 1984 有很强互补性的题找到 K 个最接近的元素。给定一个有序数组和一个目标值 target要找 k 个数使它们的值最接近 target。1984 关注的是“k 个数之间互相靠得近”658 关注的是“k 个数一起靠近一个外部锚点”。但解法上都离不开排序后的连续窗口658 可以先二分找到 target 应该插入的位置然后在这个位置附近用双指针扩展不断比较左右两边谁离 target 更近收缩出一个长度为 k 的窗口。这比 1984 多了一个二分查找的动作窗口也不再是“固定长度滑过去”而是“从中心向两侧生长”但你一定能看到熟悉的骨架有序数组、连续窗口、窗口内外的比较。做这道题的顺序建议是先 1984 再 658两个都做一遍“排序 窗口”的手感会非常扎实。4.3 延伸题二第 K 小的数对距离LeetCode 719再进阶一步看一下第 K 小的数对距离。题目让你返回数组中所有数对距离绝对值差的第 k 小值。这题最暴力的做法是枚举所有数对复杂度 O(n^2)在 n 达到 10^5 时也会超时。经典的解法是“二分答案 滑窗判定”先猜一个距离 d然后统计“有多少数对的距离 ≤ d”。如果计数不到 k说明 d 猜小了把下界往上提如果超过 k说明 d 猜大了把上界往下压。二分猜答案的外层复杂度是 O(log MaxDist)内层统计用排序 固定滑窗每一轮 O(n)。合起来是 O(n log n) 级别的解法。这里内层统计用到的滑窗和 1984 的滑窗几乎一模一样右指针遍历数组左指针保持在“第一个与右指针距离小于等于 d”的位置那么左指针和右指针之间的所有元素都能和右指针组成合法数对。把这个内层想法吃透后你再回看 1984会发现它俩共享的是同一套“有序数组 滑动窗口”的器官。4.4 面试里怎么把这题讲成加分项最后聊一点面试观感。这题是 Easy但面试官特别喜欢拿它当热身题用来观察候选人是不是“只会背题”。我建议的作答顺序是先说暴力组合数 C(n,k)复杂度不可接受说关键转折差值只由最大值和最小值决定所以应该让选中的数在数值上尽量靠近说排序依据排序后最优的 k 个数一定出现在某个长度恰好为 k 的连续窗口里说实现定长滑窗复杂度 O(n log n)收尾顺手提一句k1返回 0 的边界表示你考虑过特殊情况。这个顺序能让面试官在同一分钟内既看到你的代码能力也看到你的算法直觉。很多人知道要排序但说不清为什么排序后可以只查连续窗口——一句话的差距在评价里可能就是“会做”和“懂这道题”的差别。这道题刷完之后我个人的习惯是把它录入自己的“套路卡片”里关键词是“选 k 个、极差最小、排序窗口”。之后碰到类似描述哪怕题目包装成了矩阵、树、甚至字符串第一反应都是先想能不能排序再想能不能用窗口或双指针把枚举剪掉。坚持一段时间你会发现所谓的“每日一题”练的不是某一道题的答案而是把这种条件反射刻进脑子里。希望这篇笔记也能帮你多积累一张这样的卡片。