最近刷LeetCode热门100题的时候碰到一道有意思的题目1984. 学生分数的最小差值。题目标题自己备注了排序(类似滑动窗口)等于把核心思路直接写在脸上了。但真正动手解的时候发现这道题的坑不在于思路多难而在于你能不能一眼看出排序固定窗口这个组合以及代码实现里那些容易踩的边界细节。这篇文章我完整拆一遍从读题到推导从代码到踩坑再把滑动窗口思想怎么迁移到其他题目也聊一聊。无论你是刚上手刷题的新手还是想快速温习基础的老手都能在这篇里找到可抄作业的部分。1. 先读题题目到底在求什么1.1 从题目描述看核心需求题目给了一个下标从0开始的整数数组 numsnums[i] 表示第 i 名学生的分数再给一个整数 k。要求从数组中选出任意 k 名学生让这 k 个分数中最高分和最低分的差值尽可能小最后返回这个最小差值。这句话读起来挺绕拆开看就清楚多了。假设班里有四个人的分数是 [9, 4, 1, 7]k 2也就是每次选两个人希望这两个人的分数差尽量小。9和4差54和1差31和7差69和7差2那最小差值就是2。现在把 k 改成3你就要同时看三个人里的最高分和最低分目标还是让这个跨度尽量小。选9、4、7时最大是9最小是4差5选4、1、7时最大是7最小是1差6选9、1、7时差8。所以最小就是5对应 [9, 4, 7] 这组。题目的本质是一个组合选择问题在所有大小为 k 的子集中找到最大值减最小值最小的那个子集。注意这里选人是不要求保持原数组顺序的只要下标不同就行。1.2 第一反应为什么容易跑偏我第一次看到这题脑子里冒出的想法是先排序然后取第 k 大的减第 k 小的这个想法是错的。因为我们要选的是一组人组里的每个人都算数不是只挑两个极值就完事。比如分数 [1, 100, 101, 102]k 3如果只取极值那应该是102减100等于2感觉答案就是2。但实际上你选三个人的时候一旦选中了1组内最小就变成1差值就大了。正确的选法应该是 [100, 101, 102]差值2。这里关键是要保证整组分数在数轴上尽量聚在一起而不是单看某一对值的距离。还有一个容易跑偏的方向是暴力枚举所有组合。从 n 个元素里选 k 个组合数是 C(n, k)随便给个 n50、k25这个数就大到没法算。就算 k 很小比如 k2那也要 O(n²) 的时间数据量一大照样卡死。所以这题必须有一个更聪明的办法。1.3 数据范围与解法方向的预判LeetCode 的数据范围一般不会太离谱但也不会让暴力枚举舒服地通过。看到最小差值k个元素这种描述基本可以锁定两个方向要么排序后做贪心要么用滑动窗口。再细想一层这道题的 k 是一个固定值窗口长度固定所以天然适合排序 固定长度滑动窗口的组合。这类题目有个共性当选择不要求保持原数组顺序时排序往往是先手动作。排序虽然要 O(n log n)但跟组合数爆炸相比O(n log n) 的成本几乎可以忽略。排序之后问题会从从 n 个里选 k 个转变成在排序数组里找连续的一段搜索空间一下子小了很多。2. 核心思路排序为什么能把全局问题变成局部问题2.1 排序后最优解一定落在连续窗口这题最关键的性质是如果一组 k 个分数的差值最小那么这 k 个分数在排序后的数组中一定是连续的一段。这个性质可以用一个很朴素的替换论证来说明。假设排序后的数组是 a1 ≤ a2 ≤ ... ≤ an你选的 k 个分数里最大的是 ai最小的是 aj且 ai 和 aj 之间隔了别的没被选中的分数。也就是说排序后存在一个下标在 i 到 j 之间的分数 ak 没进组。这时候把组内当前任一极值替换成 ak组内最大值和最小值的差只会变小或者不变。为什么因为 ak 一定落在当前组的最小值和最大值之间。把一个落在区间内部的分数放进来同时踢掉一个在边界的分数整个组的跨度要么缩小要么保持不变绝不会变大。重复进行这种替换最后一定能得到一个排序后连续的 k 元素区间。所以全局最优解必然藏在排序后某个长度为 k 的连续窗口里。这个证明的思路和很多贪心题是相通的最优解具备某种紧凑结构任何一个不紧凑的方案都能通过替换变得更优或至少不差。2.2 固定长度滑动窗口的移动过程既然最优解是排序后的连续区间问题就变成了在排序数组中从左往右枚举每个长度为 k 的窗口计算窗口最右端元素减去最左端元素的差值取最小值。用前面的例子 [9, 4, 1, 7]k 2 来走一遍。排序后得到 [1, 4, 7, 9]。窗口长度是2所以有三个窗口第一个窗口从下标0开始内容是 [1, 4]差值 4 - 1 3。 第二个窗口从下标1开始内容是 [4, 7]差值 7 - 4 3。 第三个窗口从下标2开始内容是 [7, 9]差值 9 - 7 2。最小值是2和手动推的结果一致。注意窗口移动的时候我们不需要重新算窗口内部的任何东西只需要看左端和右端的差值因为窗口内部的分数再怎么样都不会影响最大值减最小值这个结果窗口两端的值就已经决定了跨度。2.3 时间复杂度拆解整个算法的时间复杂度由两部分组成排序 O(n log n)滑动窗口枚举 O(n)。总复杂度 O(n log n)空间复杂度 O(1)不计排序本身的额外空间。O(n log n) 看起来不是最优但已经非常够用。如果你愿意当分数范围很小的时候还能用计数排序把排序部分优化到 O(n range)不过题目一般没这个必要。对于这种让你任意选 k 个元素的题O(n log n) 的排序成本就是标准答案别嫌弃它。从另一个角度理解排序把搜索空间从组合级 C(n, k) 直接降到了线性级别这种降维打击才是排序的真正价值。你付出的 O(n log n) 成本换来的是后面 O(n) 的轻松扫描这笔交易非常划算。3. 代码实现与细节3.1 Java 版本直接看代码。class Solution { public int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int ans Integer.MAX_VALUE; for (int i 0; i k - 1 nums.length; i) { ans Math.min(ans, nums[i k - 1] - nums[i]); } return ans; } }Java 版本有几个细节值得专门说一下。第一个ans 初始值必须是 Integer.MAX_VALUE不能是0。因为差值再小也是正数或0如果你初始化成0Math.min 取到的一直是0正确答案就被吞了。第二个循环条件是 i k - 1 nums.length保证窗口右端不越界。有人写 i nums.length - k 1效果一样。关键是一定要搞清楚窗口右端下标和数组长度之间的关系不然 k1 时碰巧没事k 一大就数组越界。第三个为什么窗口内部不用遍历因为我们要的答案只跟窗口的最大值和最小值有关排序后窗口最大值一定是右端点最小值一定是左端点内部的元素并不影响最终差值。这个特性是整个解法能简化成这个样子的原因。3.2 Python 一行流实现Python 版本可以用生成器表达式写得很短。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))短短三行逻辑和 Java 版本完全一致。但要注意 Python 的 sort() 是原地排序会直接修改传入的 nums。在 LeetCode 上这么做没问题因为你不依赖原数组但如果在项目里写业务代码最好先 copy 一份再排序sorted_nums sorted(nums)然后把 sorted_nums 拿去做窗口扫描避免污染原始数据。这个习惯在你后续处理真实数据时特别重要毕竟谁也不想因为一个排序把原始分数列表的顺序给改了后面还要用原数组做别的统计就麻烦了。3.3 为什么不需要额外数据结构有些滑动窗口题需要维护窗口内的最大值、最小值、和、频率等状态比如滑动窗口最大值那题得借助单调队列。但本题不用因为窗口固定长度为 k而且窗口内唯一对答案有贡献的就是两端元素。换句话说这道题的窗口状态非常单薄只包含两个值起点和终点。无论窗口内部有多少个元素只要排序做好了跨度永远等于终点减起点。所以每移动一次窗口只需要 O(1) 时间做一次减法不需要任何额外空间。3.4 用最短线段来理解这道题我想再提供一个直观的理解方式。把排序后的数组想象成一条数轴上的若干点每个点是一个分数。你的任务是在这条数轴上找一条能盖住正好 k 个点的最短线段。线段长度就是从最左边的点到最右边点的距离。在数轴上盖住 k 个点且长度最短的线段一定是最左边的点和最右边的点都恰好踩在某个学生分数上。你枚举线段的左端点从第0个点一直试到第 n-k 个点右端点始终保持距离左端点 k-1 个点。每条线段的长度就是右端点减左端点。扫描完所有可能取最小值即可。有了这个画面滑动窗口四个字就非常形象了。3.5 多语言实现的统一思路再补一个 C 版本方便有 C 习惯的朋友参考。class Solution { public: int minimumDifference(vectorint nums, int k) { sort(nums.begin(), nums.end()); int ans INT_MAX; for (int i 0; i k - 1 nums.size(); i) { ans min(ans, nums[i k - 1] - nums[i]); } return ans; } };注意 C 和 Java 一样ans 初始化用 INT_MAX不要用0。数组排序用 sort(nums.begin(), nums.end())记得包含头文件 。代码的模式几乎一毛一样说明这道题的算法核心真的很简单不同语言之间的差别只在语法层面。4. 常见踩坑与边界用例4.1 最容易错的三种写法第一种错循环条件写错。有人图省事写 i nums.length循环体里直接取 nums[i k]这样 k 大于1时最后几次循环一定会越界。正确写法要么是 i k - 1 nums.length要么是 i nums.length - k。第二种错ans 初始值设成0。这是我见过最多的低级失误。初始化成0后min 运算永远不会更新最后答案永远是0。尤其是刚从其他语言转过来的朋友容易把 ans 初始习惯写成0。正确做法是初始化成一个足够大的值比如 Integer.MAX_VALUE 或 Python 的 float(inf)。第三种错忘了排序。这道题不排序硬做只能回到组合暴力。虽然理论上还是能做但复杂度直接起飞。我个人觉得 LeetCode 上出现忘记排序这样的失误比较少但确实见过有人把窗口滑动逻辑写对了就是没给数组排序最后答案全错。遇到这种题排序应该作为条件反射一样的第一步动作。4.2 边界用例速查整理一个边界用例表格方便你自测代码。输入k期望结果说明[90]10只有一个学生选1人差值为0[9,4,1,7]22选[7,9]差为2[9,4,1,7]35选[4,7,9]差为5[1,1,1,100]20两个重复的1差为0[1,3,7,10]49全选最大值10减最小值1k 1 的时候每个窗口的左右端是同一个元素差值全是0所以答案必然是0这个边界情况不用单独处理代码天然正确。k n 的时候只有一个窗口答案就是整个数组的最大值减最小值也是天然覆盖。重复分数的场景下排序后相同的分数会相邻窗口内如果出现两个相同分数差值就能取到0同样没问题。4.3 编码层面的隐蔽细节还有一个细节容易被忽略当数组长度小于 k 的时候怎么办LeetCode 题目保证 k 不会超过数组长度所以可以不考虑。但如果你在实际业务场景里封装这个逻辑最好加一个防御性判断比如 if (k nums.length) return -1 或抛异常。否则窗口扫描逻辑在 k 比数组还大的时候会直接算出奇怪的结果。负数分数的场景也可以顺带验证。题目说是学生分数一般是非负整数但排序的思路对负数同样有效。比如 [-5, -1, 0, 3]k2排序后的窗口 [ -1, 0 ] 差1就是最优解。说明这个算法不依赖分数为正只要差值定义是大减小就行。性能方面再提一句Python 的生成器表达式虽然简洁但对十万级的数据会有轻微额外开销。如果你在竞赛或性能敏感的场景可以先算好长度用显式 for 循环保留中间最小值。不过这题的 n 通常不大怎么写都能过。从锻炼代码风格的角度看Java 和 C 那种先取最大值再逐步更新的结构反而更贴近很多工程代码的写法。5. 从这道题延伸出去的滑动窗口思维5.1 固定窗口与可变窗口的本质差别固定窗口窗口长度不变从左往右滑一般只需要枚举起点或终点就行。滑动窗口最大值、字符串排列匹配这类题用的就是固定窗口。可变窗口两个指针右指针负责扩大窗口左指针负责在条件不满足时收缩窗口专门解决满足某个条件的最短/最长子数组问题。比如无重复字符的最长子串、长度最小的子数组都属于这一类。两者的共同点是都利用数组的某种单调性避免重复计算。区别在于固定窗口不需要维护窗口内部的复杂信息只要把窗口起点挪一下就行可变窗口则要时刻判断当前窗口是否满足条件并相应移动左指针。理解了这道题的固定窗口逻辑再去看可变窗口的题你会发现自己对窗口两个字的敏感度提高了不少。5.2 相关题目与难度对照做过几道相关题目之后我列了一个自己刷下来感觉难度有梯度的列表长度最小的子数组LeetCode 209可变窗口入门题求满足和大于等于 target 的最短子数组长度。无重复字符的最长子串LeetCode 3可变窗口 哈希表统计字符频率窗口内状态要实时维护。滑动窗口最大值LeetCode 239窗口长度固定但要求窗口内最大值必须借助单调队列。学生分数的最小差值LeetCode 1984固定窗口窗口只关心首尾最容易上手。想系统练滑动窗口的话按这个顺序刷从简单到复杂进步会比较明显。尤其是从1984这道题切入你会发现固定窗口几乎是所有滑动窗口变体里最安全、最好写的一类。5.3 怎么快速识别排序窗口题型以后再做新题可以按三个信号判断是否要套用排序窗口思路。第一题目说从数组中任意选择若干个元素强调任意选择意味着顺序不重要排序是安全的。如果题目要求连续子数组或保持原有顺序那排序就要谨慎了大概率不是这条路。第二优化目标跟最大值与最小值的差有关也就是说跨度是核心指标。排序之后任何子集都可能落在一段连续区间里跨度可以用首尾差快速求出。第三选取数量 k 是固定的或者可以二分枚举。固定 k 的时候直接固定窗口不固定 k 时往往需要配合二分比如最小化最大值这类问题排序后对答案二分再用窗口验证可行性。只要这三个信号同时出现你基本可以确定解法第一步是排序第二步是窗口扫描。这套判断法帮我快速解决了不少类似的题目比如子序列最小差值、划分后的区间跨度优化等都是同一套底层逻辑。我个人刷题下来最大的感受是这题别看简单它把排序降维和滑动窗口两个基础工具拧在一起让你体会到了组合优化问题如何被结构化转成线性扫描。你学会的不只是一道题的解法而是遇到任意选取 k 个元素求最小跨度这类问题时能条件反射地想到排序。最后分享一个小技巧拿到这类题先别急写代码在纸上画几个分数点手动挑出最优组合。你很快会发现每次最优解都长得像排序后挨在一起的一撮人。这个规律只要亲手验证过一次后面写代码就是水到渠成的事。