1. 题目拆解与核心思路1.1 题目到底在求什么LeetCode 每日一题刷到 1984 学生分数的最小差值题面其实一句话就能说清楚给你一个整数数组 numsnums[i] 表示第 i 名学生的分数再给一个整数 k要求从这些学生中任选 k 个使得这 k 个分数里的最大值与最小值之差尽可能小最终返回这个最小的差值。举个例子nums [9, 4, 1, 7]k 2从四个学生里挑两个人两个分数可能相差多少穷举一下9 和 4 差 59 和 1 差 89 和 7 差 24 和 1 差 34 和 7 差 31 和 7 差 6。最小差值就是 2所以返回 2。如果 k 1只选一个学生最大值和最小值都是他自己答案恒为 0。这道题的数据范围给得相当温和数组长度不超过 1000k 不会大于数组长度分数在 0 到 10^5 之间。按照这个规模就算写一个稍微笨一点的算法也大概率能通过。但这道题的价值不在能不能过而在它背后的两个关键思考为什么要排序为什么排序后扫一遍就能得到答案这两个问题想透了后续很多同类题都会轻松不少。1.2 第一反应为什么容易跑偏我第一次做这题时的第一反应是组合枚举从 n 个学生里选 k 个把所有选法都列出来逐个算极差取最小值。这个思路数学上没错但计算量完全不能接受。C(n, k) 在 k 接近 n/2 时是个天文数字n 取 1000、k 取 500 时即使只做最基础的加减法也不可能在限时内算完。所以暴力枚举只能作为小数据验证答案的工具不能作为正式解法。还有一种很容易出现的错误想法既然要差值小那就排完序直接取分数最低的 k 个。这个方案有一个很直观的反例nums [1, 50, 51, 100]k 2。分数最低的两个是 1 和 50差值是 49可是正确答案应该是选 50 和 51差值是 1。分数最低的一批学生不代表他们在分数上抱团可能只是整体偏低但内部散得很开。还有人会想直接找全局最大值和全局最小值这同样不对。题目不是让你把全部学生都选上只选 k 个全局极差和局部极差是两码事。这道题真正要找的是分数轴上最密集的那一段。1.3 排序是破局点为什么排序能成为破局点因为排序把数值上的接近变成了下标上的邻近。假设排序后的数组是 a[0] a[1] ... a[n-1]那么任选 k 个数最后决定极差的只有这群数里的最小值和最大值也就是排序后最靠左和最靠右的两个点。为了让极差尽可能小这 k 个点应该尽量挤在一起。打个比方你在一列地铁站里想选 k 个连续站台希望首尾两站之间距离最短。站台在数轴上的位置是固定的那最短的一段必然是连续 k 个站台因为中间如果跳过某个站台只会让首尾拉得更远没有任何好处。数组排序后这个直觉就完全可以数学化了。所以整个算法的主线就很清晰先排序然后用一个长度固定为 k 的窗口从头扫到尾记录所有窗口内最大分数与最小分数之差取最小。剩下的问题就是这个做法为什么一定正确接下来我们把证明补完整。2. 从排序到滑动窗口正确性说明2.1 为什么最优解一定落在排序后的连续窗口里这一步是整道题的核心也是面试时很值得讲清楚的部分。我们可以用构造法来证明而不是只背结论。假设我们有一个最优方案选出了 k 个学生在排序后的数组里这些学生对应的最小下标是 l最大下标是 r。因为从 l 到 r 这个区间里至少要包含 k 个元素否则不可能选出 k 个人所以一定有 r - l 1 k。接下来做一个构造直接取排序后从 l 开始的连续 k 个元素也就是 a[l], a[l1], ..., a[lk-1]。由于刚才已经确认 r - l 1 k所以 l k - 1 不会超过 r。数组是升序的因此这个新集合的最大值 a[lk-1] 一定不超过原方案的最大值 a[r]而最小值仍然是 a[l]。于是新集合的极差是 a[lk-1] - a[l]它必然小于等于原方案的极差 a[r] - a[l]。换句话说任何一个最优方案都能被改造成一个连续 k 个下标的方案而且结果不会变差。既然如此我们只需要扫描所有长度恰好为 k 的连续子数组就够了完全不用去枚举组合。面试时讲解这个结论重点是构造法任意最优方案都能改造成某个连续窗口且差值不会变大因此扫描连续窗口就能覆盖全局最优解。把这个证明说清楚比单纯背出排序滑窗四个字有用得多。再换一个更直观的视角如果你随手选了 k 个点这些点之间有空隙那么把中间空隙处那些没被选中的点补进来同时把最外侧的某个点替换成更靠内的点首尾距离只可能缩短不可能拉长。既然空隙没有价值最优解自然倾向于落在连续的一段上。2.2 一次遍历完成统计当数组排好序窗口长度固定为 k 时实现就非常直接了。对每个可能的窗口左端点 i右端点就是 i k - 1这个窗口内最大值是 a[ik-1]最小值是 a[i]极差就是两者相减。我们用一个 ans 变量记录所有窗口极差的最小值。用示例推演一遍nums [9, 4, 1, 7]k 2排序后变成 [1, 4, 7, 9]。窗口从下标 0 开始i 0窗口 [1, 4]差值为 3i 1窗口 [4, 7]差值为 3i 2窗口 [7, 9]差值为 2。最终答案就是 2。和手工穷举的结果一致。这里值得注意的是滑动窗口里并不需要维护什么复杂结构比如单调队列或者堆。原因很简单本题只需要窗口的最大值和最小值而在排序后的数组里这两个值天然就在窗口的两端。其他经典滑动窗口题之所以要用队列或哈希表维护窗口状态是因为窗口内的最大值/最小值会随元素的加入和离开而变化但本题排序后这个变化是确定的直接读端点即可。2.3 复杂度分析时间复杂度由两部分组成排序是 O(n log n)扫描所有窗口是 O(n)所以整体复杂度是 O(n log n)。这个复杂度在 n 1000 的条件下非常宽松即便 n 放大到 10^5排序加一次线性扫描也能很轻松地完成。空间复杂度要看排序实现。Java 的 Arrays.sort 对基本类型数组是原地排序Python 的 list.sort 也是原地C 的 sort 同样不申请和 n 相关的额外空间所以本题的额外空间复杂度可以认为是 O(1)。如果你使用 Python 的 sorted()那会生成一个新的排序后列表额外空间就是 O(n)不过题目规模下也完全够用。还有一个值得想的点比较排序的理论下界是 O(n log n)所以本题在任意分数范围的前提下O(n log n) 已经是一类很好的复杂度。只有当分数范围被限定时才能通过计数排序把排序部分再优化到 O(n C)这部分我在第 4 节会展开讲。3. 三种语言实现与细节处理3.1 Java 版本INF 的取法和循环边界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; } }两个细节值得说一下。第一ans 初始值取 Integer.MAX_VALUE。这个值看着夸张但完全安全因为分数的最大差值不超过 10^5永远不会溢出。如果你非要严谨也可以取 100001 这种比最大可能答案更大的值不过写 Integer.MAX_VALUE 更省心不用动脑算边界。第二循环条件我写的是i k - 1 nums.length意思是窗口右端点不能越界。有些同学喜欢写成i nums.length - k 1两者数学等价。关键是别写成i nums.length否则 i 接近数组末尾时i k - 1会越界程序直接报错。另外k 1 时其实不需要特判。窗口只有一个元素差值恒为 0循环自然会把 ans 更新成 0。提前返回 0 当然也可以只是多了个分支而已。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))这里nums.sort()是原地排序直接修改原数组不额外生成新列表。如果你用sorted(nums)虽然也能得到有序数组但会多一份 O(n) 的内存开销在这道题里影响不大但不必要的浪费能省就省。后面那个min(... for ...)是生成器表达式和列表推导式[... for ...]不同生成器是惰性求值的不会先把所有差值算出来存进一个列表。如果 n 很大这个写法在内存上更友好。当然如果你觉得一行版本阅读性不够完全可以展开写class Solution: def minimumDifference(self, nums: List[int], k: int) - int: nums.sort() ans float(inf) for i in range(len(nums) - k 1): ans min(ans, nums[i k - 1] - nums[i]) return ans两种写法逻辑完全一样。我个人在 LeetCode 上会直接提交一行版但在笔记里会保存展开版因为展开版更容易让未来的我快速理解。3.3 C 版本sort 与 INT_MAXC 的实现如下class Solution { public: int minimumDifference(vectorint nums, int k) { sort(nums.begin(), nums.end()); int ans INT_MAX; for (int i 0; i k (int)nums.size(); i) { ans min(ans, nums[i k - 1] - nums[i]); } return ans; } };一个容易踩的坑是nums.size()返回的是无符号的 size_t如果直接用i k nums.size()比较左边是 int右边是 size_t会发生隐式类型转换。虽然这道题的边界条件保证了不会出问题但为了代码严谨我通常会强转成(int)nums.size()。这个习惯在写更复杂的二分或者双指针题目时能帮你避免很多藏在类型转换里的 bug。C 的sort在底层是内省排序综合了快排、堆排和插入排序的优势性能很稳。LeetCode 环境通常已经包含了必要头文件本地编译时记得 includealgorithm和climits。3.4 边界条件自查表刷题时建立一张边界自查表能省掉大量调试时间。这道题常见的边界情况整理如下场景结果说明k 10单个学生最大值等于最小值k n数组最大值 - 最小值只有唯一一个窗口所有分数相同0任何窗口差值都为 0分数包含 0 和 10^5最大可能差 10^5不会撑爆 int窗口右端点越界循环条件防护注意 i k - 1 的下标写法另外我建议写完代码后用暴力枚举做一个随机对拍尤其适合这种数据范围小的题目。比如用 Python 的 itertools.combinations 写一个暴力版本随机生成几百组小数组对比自己的滑窗解法和暴力结果是否一致。这个方法能快速暴露下标边界错误比肉眼检查可靠得多。注意i k nums.length和i k - 1 nums.length是等价的别在两种写法间反复横跳选定一种写熟能减少很多边界上的低级错误。4. 常见问题与调试实录4.1 为什么要排序为什么不需要动态双指针有位读者问我既然题目叫滑动窗口为什么不用 left 和 right 两个指针动态伸缩这是个好问题。滑动窗口的核心在于控制一段连续区间但本题的窗口长度是固定的 k。固定长度的窗口遍历左端点就足够了右端点永远是左端点加 k 减一。真正的双指针滑动窗口通常用于窗口长度动态变化的场景比如找一个子数组使得和不超过某个值找最长连续子序列之类。排序的必要性前面已经讲过这里再强调一下。如果不排序连续下标和数值接近没有任何对应关系你根本无法用窗口去枚举最密集的一段。排序这一步不是可有可无的锦上添花而是整个算法成立的地基。我在实际调试中还发现一个有意思的现象有人会先写一个不排序的版本然后用一个堆去维护动态窗口里的最大最小值试图模拟滑动窗口求极差的通用做法。这个思路放在原始数组上的可变窗口求极值是可以的但在这道题里属于过度设计。既然能 O(n log n) 排序后 O(n) 扫完何必用对数复杂度的堆去维护一个本来可以预知顺序的数组呢4.2 k 1 和 k n 的极端情况这两个极端情况我放在一起说因为它们是同一个道理主流程天然覆盖不需要额外特判。k 1 时窗口只有一个学生最高分和最低分都是同一个分数差值为 0。无论数组怎么排循环都会把所有窗口差值算成 0最终 ans 返回 0。k n 时整个数组就是唯一的窗口循环只需要跑一次答案就是nums[n-1] - nums[0]。但我在本地测试时见过一个反例就是因为有人做了特判反而写错了他写if (k 1) return 0;之后把 ans 初始化成了nums[0]然后直接开始循环。当 k 1 时如果第一个窗口差值恰好大于nums[0]ans 就不会被正确更新导致答案偏小。所以我的建议是先让一般性代码正常工作再考虑特判而且特判不要改变 ans 的初始化逻辑。4.3 重复分数会影响结果吗不会。分数重复只是让排序后的数组里出现连续相等的值窗口差值可能变成 0这本来就是最小可能值不影响算法正确性。举个例子nums [1, 1, 1, 100]k 2排序后是 [1, 1, 1, 100]。窗口 [1, 1] 的差值是 0扫描会正确返回 0。极端一点如果所有学生分数完全一样比如 [7, 7, 7]k 2窗口差值全是 0返回 0。这个直觉和稳定的排序算法很重要吗无关因为本题只关心分数大小同分数的学生顺序无所谓。4.4 数据范围如果放大怎么办计数排序与二分答案原题 n 1000用比较排序当然最舒服。但面试或扩展训练时经常会被追问如果 n 很大怎么办。第一个优化方向是计数排序。因为分数范围被限定在 0 到 10^5我们可以用频率数组在 O(n C) 时间内得到有序序列其中 C 是分数最大值。代码长这样def minimum_difference_with_counting(nums, k): max_score max(nums) freq [0] * (max_score 1) for x in nums: freq[x] 1 sorted_nums [] for score in range(max_score 1): if freq[score]: sorted_nums.extend([score] * freq[score]) ans float(inf) for i in range(len(sorted_nums) - k 1): ans min(ans, sorted_nums[i k - 1] - sorted_nums[i]) return ans这个思路的核心是利用有限的值域用计数的方式天然完成排序再套原来的窗口扫描。代价是多一个 O(C) 的计数数组以及重建有序序列的 O(n) 额外空间。如果不想重建数组还能直接在 freq 上做双指针维护分数值区间内至少有 k 个学生的最小区间跨度思路类似但实现细节更多面试时容易绕晕。第二个优化方向是二分答案 滑动窗口判断。如果问题变成判断是否存在 k 个学生的极差不超过 mid那么排序后可以双指针检查右指针不断右移左指针收缩到最大值减去最小值不超过 mid的最左位置只要区间长度达到 k就说明可行。于是外层二分 mid内层 O(n) 判断整体 O(n log C)。def can(nums, k, mid): left 0 for right in range(len(nums)): while nums[right] - nums[left] mid: left 1 if right - left 1 k: return True return False def min_diff_binary(nums, k): nums.sort() lo, hi 0, nums[-1] - nums[0] while lo hi: mid (lo hi) // 2 if can(nums, k, mid): hi mid else: lo mid 1 return lo这种二分答案的思想在很多题目里都通用比如很经典的爱吃香蕉的狒狒那类题表面上是在二分一个速度值本质也是在判断某个答案是否可行的框架里做文章。刷每日一题时如果能顺手把一个简单题往这个方向延伸收益远比多刷几道重复题大。5. 类似题型与我的复盘方法5.1 从最小差值到最长区间的变式原题是固定选 k 个让极差最小。稍微改一下条件就变成另一类经典题不限制人数只限制极差不能超过 limit问最多能选多少个学生。做法依然是排序加双指针def max_students(nums, limit): nums.sort() left 0 ans 0 for right in range(len(nums)): while nums[right] - nums[left] limit: left 1 ans max(ans, right - left 1) return ans右指针每扩展一次左指针就收缩到合法的最左位置窗口里的人数就是当前右端点为结尾时的最大可选人数。这个变式和原题共享同一个核心认知排序之后区间内任意两点的极差只由两端决定窗口的伸缩完全可以用双指针维护。再往后延伸如果题目改成选 k 个分数使得方差最小排序后依然滑动窗口只不过在窗口移动时要额外维护窗口内元素的和与平方和用来快速计算方差。数据结构变复杂了但排序后连续窗口包含最优解这一证明骨架完全不变。这些变式看起来千变万化底层全是排序加滑动窗口的组合。真正把一道 Easy 题吃透不是记住它的代码而是记住它背后的这个骨架。5.2 这类题在周赛里的位置很多周赛的 A 题、B 题就是这种排序 线性扫描的套路。它不一定难但特别考验两点第一能不能迅速识别出排序带来的结构简化第二能不能把下标边界一次写对。比赛和平时刷题不一样时间压力很大。如果第一道题就卡在要不要用组合枚举窗口边界怎么写上后面中等题和难题的时间会被严重压缩。所以我一直建议像 1984 这种模板题要练到肌肉记忆看到任意选择 k 个 最小化最大值/差值或者限制极差 问最多能选多少个第一反应就该是排序然后顺着排序后的数组思考窗口或者双指针。当然遇到的新题不一定完全照搬模板但先排序再分析的思路几乎不会错。因为排序能把无序集合这个难题转化为有序区间这个可枚举的结构这是很多题目最关键的降维操作。5.3 我的每日一题复盘节奏最后分享我刷每日一题的习惯特别是这种简单题。第一步不看题解自己先写一个能过的版本哪怕暴力也行。暴力版本不是为了提交而是为了让大脑先建立对题目的直观感受知道答案大概长什么样。第二步去看题解区高赞答案尤其看别人的证明过程而不是只抄代码。比如这道 1984最重要的知识点不是那几行滑窗代码而是为什么最优解一定落在连续窗口里的构造性证明。第三步把题目归档进自己的模板库记下标签、复杂度、易错点再顺手想一个变式。以这题为例我的笔记大概是标签排序、滑窗、极差最小化复杂度排序 O(n log n)扫描 O(n)易错点窗口右端点下标 ik-1 越界ans 初始值取 INF变式极差不超过 limit 时最多选多少人用双指针二分答案判断是否存在 k 个极差不超过 mid 的人数。这样一条笔记写下来只需要两三分钟但下次再遇到同类型题目搜索记忆时非常快。说实话我刚开始刷 LeetCode 时也迷信题海战术一天刷十几道结果一周后基本忘光。后来改成一天一道但把一道题从证明到扩展全部吃透反而效率高很多。最后再分享一个小技巧写完这道题后不要急着马上提交先手动跑几个边界用例比如 k1、kn、数组全相同、数组升序排列、数组降序排列。这些用例能帮你确认下标逻辑没有隐藏 bug也能让你在评论区看到别人问为什么我 k1 会错时一眼就知道问题出在哪。LeetCode 的每日一题其实是一个很好的训练节奏只要每次都能把一个简单题挖出一点新东西日积月累下来比盲目刷几十道重复题要扎实得多。