1. 题目拆解与思路铺垫1.1 从题目描述到核心矛盾LeetCode 每日一题又来了今天这道 1984. 学生分数的最小差值乍一看名字就很有校园味但本质是一道非常经典的“排序 滑动窗口”入门题。题目的输入是一个整数数组scores和一个整数k要求从数组里选出k名学生的分数使得这k个分数中的最大值与最小值的差尽可能小最后返回这个最小差值。很多第一次刷这道题的朋友第一反应可能是“把所有组合都枚举一遍挑差值最小的”。思路没问题但稍微估算一下复杂度就明白了如果数组长度是n选出k个数的组合数是C(n, k)当n到 100、k到 50 的时候这个数字已经大到计算机根本算不完。题目给的scores.length最大是 1000所以暴力组合必然不可取。核心矛盾其实就一句话如何在不需要枚举所有组合的前提下快速找到“最紧凑”的k个分数。这道题适合正在准备面试、刷 LeetCode 热题 100 的朋友作为滑动窗口的入门练手也适合想巩固排序思维的老手快速过一遍。因为它的解法非常典型窗口移动的边界处理也很有代表性弄懂这道题很多“子数组 / 子序列最值”类的题目都能顺势拿下来。1.2 为什么是排序 滑动窗口先想一个生活中的例子假设你从一堆乱放的纸条里抽 5 张想尽量让抽到的数字接近你会怎么做正常人都会先把纸条按数字从小到大排好再随手挑连续的 5 张看看。因为一旦排序后任意连续的k个元素它们的最大值和最小值就是区间的两端而区间外的元素只会让差值更大所以最优解一定藏在排序后的某个连续区间里。这就是这道题最核心的观察排序之后问题从“在无序数组中找 k 个元素”变成了“在有序数组中找长度固定为 k 的最小区间”。暴力枚举区间的起点需要 O(n) 次每次计算区间最大最小差值如果每次都重新遍历一遍区间那整体还是 O(n*k)。但我们可以用一个非常巧妙的方法窗口右端每向右移动一步左端也跟着移动一步始终保持窗口长度为k然后只需要计算scores[right] - scores[left]就能得到当前窗口的差值。为什么从“选 k 个”变成“找连续 k 个”是安全的因为排序后如果最优解不是连续的 k 个元素那么它中间一定漏掉了某些元素而这些被漏掉的元素值必然落在最优解的最小值和最大值之间。把漏掉的元素加进来最大值不会变大最小值不会变小差值只可能不变或变小同时元素个数增加。既然题目只要选 k 个那我们完全可以抛掉多余的元素换成一个更紧凑的连续区间。因此最优解必然对应某个连续的 k 区间这个结论是滑动窗口解法成立的地基。2. 排序解法与滑动窗口实现2.1 排序预处理为什么先花 O(n log n) 的成本有人可能会问排序本身就要 O(n log n)是不是反而变慢了这里要纠正一个直觉。暴力组合是 O(C(n,k))这是个灾难性的复杂度而排序的 O(n log n) 在 n1000 时几乎可以忽略不计。排序所付出的代价换来的是后续窗口扫描只需要 O(n) 的线性时间总体复杂度从指数级降到了对数线性级这是性价比极高的交易。具体到代码排序可以直接用语言内置的排序函数比如 Python 的sorted()或 C 的sort()。排序之后数组变成了单调不减的序列。这时任意长度为k的连续子数组其“最大值 - 最小值”就是nums[ik-1] - nums[i]。我们只需要遍历每一个可能的窗口起点取所有差值中的最小值即可。这里有一个很有意思的点排序之后为什么窗口内的元素“越紧凑越好”因为我们要的是“最小差值”而排序后的数组里相邻元素的差已经是最小的局部差异长度为 k 的窗口会把 k 个元素尽量框在一起框住的元素在数值上天然是接近的。如果窗口跨越了数组中很远的两个位置差值就会变大所以我们要在所有窗口里找最小值。2.2 滑动窗口的核心维护逻辑滑动窗口的代码模板其实很固定。以 Python 为例核心部分是def minimumDifference(nums, k): nums.sort() left 0 right k - 1 ans float(inf) while right len(nums): ans min(ans, nums[right] - nums[left]) left 1 right 1 return ans这个写法里窗口用left和right两个指针表示初始时窗口覆盖数组前 k 个元素。每轮循环计算当前窗口的最大最小值差值然后两个指针同时右移一格相当于窗口向后滑动一步直到右指针越界。整个过程只需要一次遍历所以窗口部分的时间复杂度是 O(n)。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; } };注意这里i k - 1是窗口右端下标循环条件是“右端不越界”。很多新手会写成i nums.size() - k这种写法在k等于 0 或大于数组长度时会出错。而用i k - 1 nums.size()这种写法天然处理了边界情况。另外题目中k最小可能是 1这时窗口里只有一个元素最大值和最小值都是它自己差值恒为 0所以直接返回 0 也是符合逻辑的。2.3 为什么窗口每次只移动一格而不是跳着移动这是我在评论区经常看到的一个疑问既然要找差值最小的窗口为什么不能先排序然后直接比较相邻元素取连续 k 个中首尾差值最小的为什么必须老老实实一格一格滑动其实“相邻比较”也是滑动窗口的一种简化表达本质上还是遍历每个起点。只不过有些题解会用双指针直接维护窗口内的什么东西比如维护最大值、最小值、窗口和等这道题因为排序后窗口的最大最小值就是两端所以不需要维护额外数据结构只需要比较首尾差值就够了。滑动窗口的“滑动”本质上是枚举所有可能的连续区间。它相比暴力枚举的优势在于每次窗口移动时只有两个元素发生变化一个出窗、一个入窗我们可以利用上一次的计算结果快速得到新窗口的结果。但在这道题里由于最大值最小值就是两端所以甚至不需要依赖上一次的结果直接算就行。理解了这一点后续遇到“窗口内需要维护复杂状态”的题目时才能真正明白滑动窗口为什么高效。3. 复杂度分析与其他解法对比3.1 时间复杂度与空间复杂度的严谨推导先看时间。排序使用内置排序平均 O(n log n)最坏也是 O(n log n)。排序后的一次循环循环次数是n - k 1次每次只做一次减法、一次比较所以是 O(n)。整体时间复杂度就是 O(n log n n)习惯上写成 O(n log n)因为排序主导。空间复杂度取决于排序实现。Python 的sorted()会新建一个列表占用 O(n) 额外空间C 的sort()是原地排序如果忽略递归栈空间复杂度是 O(1)。所以如果用 C 写可以做到常数空间用 Python 写则 O(n) 空间。实际刷题时这个差别在 1000 的量级下完全无感。有些题解会用“计数排序”或“桶排序”来做因为题目中分数范围可能有限比如 0 到 100那确实可以做到 O(n range) 时间。但 LeetCode 的官方题解并没有限制分数范围所以通用解法还是排序 滑动窗口。实际面试中你抛出计数排序的想法可能会让面试官眼前一亮但实现起来要额外处理桶的扫描反而更容易出错。我的建议是先掌握标准解法有余力再谈优化。3.2 暴力解法的缺陷与滑动窗口的不可替代性暴力枚举所有 k 元组合即使剪枝也会卡在组合数爆炸上。拿n1000, k500来说C(1000, 500)是一个超过 300 位数字的恐怖数值任何计算机都跑不完。所以排序 滑动窗口几乎是这类“固定个数最小差值”问题的标准答案。但滑动窗口并不是所有“最小差值”题都能用。它之所以有效正是因为数组是有序的。如果题目不允许排序或者要求在原数组顺序下选 k 个元素即子序列但保持相对顺序那排序就直接破坏了顺序问题会变得复杂得多。比如“从原数组选 k 个下标使最大最小差值最小”且“不允许重排”那就需要用二分答案 滑动窗口统计可行性来解决。这是另一个维度的问题竞赛里很常见。这道题因为学生分数没有“相对顺序”要求所以可以放心排序。我们不妨把几种思路放在一个表里对比解法时间复杂度空间复杂度适用场景风险点暴力组合O(C(n,k))O(k)n 极小比如 20n 稍大就超时排序 滑动窗口O(n log n)O(1)原地排序通用k 边界处理计数排序 扫描O(n range)O(range)分数范围有限范围大时爆炸二分答案 窗口O(n log(max-min))O(1)求最小差值且可判定实现复杂从表里能看出排序 滑动窗口是普适性和简单性的最佳平衡点。这也是 LeetCode 把它定位为“简单/中等”题的原因。不过题目实际难度评级是“简单”但如果不知道“排序后连续区间最优”这个关键观察照样会卡住。所以这道题对思维训练的含金量不亚于一些中等题。4. 常见错误与调试心得4.1 最容易踩的坑窗口大小与边界条件我在这道题的评论区见过最多的错误集中在三个地方。第一个是把k当成数组下标而不是个数。比如k3窗口应该包含 3 个元素右端下标是left 2也就是left k - 1。有人会写left k那窗口就变成 4 个元素了结果自然不对。这类错误在样本少的时候很难发现因为可能恰好差值碰巧对了但提交后就会在隐藏用例上翻车。第二个是没有处理k 1的特殊情况。当k 1时窗口只有一个元素最大值和最小值相等差值恒为 0。循环里如果用nums[ik]来做右端必然数组越界但如果用i k - 1就会发现窗口长度为 1 时也能正常遍历不需要特判。所以我在写代码时一律用i k - 1这个模式从根上避免越界。第三个是误以为“排序后只比较相邻元素的差值”就够了。有人会直接用min(nums[i1]-nums[i])然后乘以k-1这是不对的。因为相邻元素差的最小值只代表两个元素最接近但窗口里可能混入一个很大的值导致整个窗口差值很大。必须老老实实比较窗口两端的差值而不是简单把相邻差值叠加。这个误区对新手很有迷惑性我在实际辅导别人刷题时几乎每次都要强调。4.2 实际提交中遇到的性能与精度问题理想很丰满现实很骨感。虽然理论上 O(n log n) 对于 n1000 来说非常快但如果你在循环体内做了多余操作比如每次重新切片nums[i:ik]再求max/min那复杂度就退化成 O(n*k) 了n1000 时虽然也能过但这不是我们要的优雅解法。LeetCode 的判题系统有时候很宽容但面试时面试官不看代码细节一看到你切片大概率要追问复杂度所以习惯要从刷题就开始养成。另一个小坑是初始值。我有很多次把ans初始化为nums[-1] - nums[0]或 0结果如果数组本身有负数或者k为 0就会出错。最稳妥的方式是初始化为一个超大值比如 Python 的float(inf)或 C 的INT_MAX然后不断取最小值。这样即使数组只有一个元素也能正确返回 0因为循环内的min会把inf替换掉。有朋友问过如果k0怎么办题目规定1 k scores.length所以不需要担心。还有一点是关于排序的稳定性。这道题用到的排序只关心值的大小不关心相同值的相对顺序所以用sort()即可。如果题目要求输出分数对应的学生 ID那就需要存成元组后排序并自定义排序规则。这道题没有这个要求但很多变式题会加这个条件提前知道有好处。4.3 调试技巧用最小例子推演窗口移动我在本地调试这道题时建议用一个只有 4 个元素的数组手动走一遍。比如nums [9, 4, 1, 7],k 2。排序后变成[1, 4, 7, 9]。窗口长度为 2起点分别是 0、1、2差值分别是 3、3、2所以答案是 2。这个例子里最优窗口是[7, 9]它并不是数组中最靠前的两个元素而是靠后的两个这能帮你理解为什么必须遍历所有窗口而不是只看开头。如果你用的是 Python可以在循环里打印left和right以及差值。比如nums [9, 4, 1, 7] k 2 nums.sort() for i in range(len(nums) - k 1): print(i, i k - 1, nums[ik-1] - nums[i])输出会清晰展示每次窗口的变化。这种“带打印调试”的习惯在真实项目和笔试中都很实用。面试时如果卡在边界直接在白板上画窗口的移动轨迹比闷头想代码更快。5. 变式与扩展训练5.1 如果将 k 变成区间怎么办这道题给定固定k但 LeetCode 上有许多同门师兄弟比如“最小覆盖子串”“长度最小的子数组”等它们不要求固定长度而是要求满足某个条件下的最短/最小区间。如果你把这道题变一下不固定k而是给定一个最大差值maxDiff求最少选多少个连续学生能覆盖这个差值这就是另一道经典题“区间内最大差值不超过 X 的最短子数组”。解法变成了二分答案 滑动窗口每次窗口内如果nums[right] - nums[left] maxDiff就移动左指针。这个过程正好和今天的固定窗口相反但核心思想一脉相承。理解这种变式的好处是你在面对 LeetCode 热题 100 中的滑动窗口系列时会形成知识网络。比如 3. 无重复字符的最长子串用的是可变窗口209. 长度最小的子数组用的也是可变窗口而 1984 用的是固定窗口。把固定窗口和可变窗口放在一起对比你会发现它们只是指针移动策略的差异固定窗口左右指针一起动可变窗口则根据条件单边动。这个抽象一旦建立滑动窗口题就不再是背模板而是真正的理解。5.2 与 LeetCode 热门题和周赛题目的横向联系最近 LeetCode 周赛 430 的题解里也有不少滑动窗口的应用很多同学觉得周赛题难其实是因为没有把基础题吃透。1984 这道题就是滑动窗口的最小单元——固定长度窗口。掌握它之后再看周赛里那些“求固定长度窗口内最大最小差值之和”“求所有长度为 k 的子数组的极差平均值”之类的题会发现骨架都是同一个。LeetCode 热门 100 题中基本上所有滑动窗口题都遵循一个套路先确认窗口是固定还是可变再确认窗口维护的信息是什么极值、和、计数、哈希集合等最后确定指针移动时机。1984 的窗口维护的信息就是“最大值和最小值”而因为排序这个信息可以直接通过两端下标获得。如果哪天你遇到一个“不能排序”的题那么窗口维护极值就不能靠下标了得用单调队列。比如 239. 滑动窗口最大值那就是用双端队列维护窗口内最大值每次移动 O(1)。这道题可以作为滑动窗口的进阶目标。另外这道题的 Java 题解也值得看看语言特性。比如 Java 的Arrays.sort是原地排序循环用for (int i 0; i k - 1 nums.length; i)返回值同理。多个语言对比之后你会发现算法本身与语言无关但边界细节会因为语言的数组越界机制而不同。比如 Python 切片越界不会报错只是返回空列表这容易掩盖 bug而 Java/C 越界直接抛异常或未定义行为反而更容易暴露问题。5.3 从刷题到面试这道题考察的底层能力面试中考滑动窗口不只是考你会不会这个算法更考你对“有序性”的敏感度。拿到题目你能否迅速想到排序这就是数据有序化思维的体现。很多算法题的突破口都是“先排序再处理”比如求两数之和的变体、合并区间、三数之和等都利用了有序性。所以 1984 这道简单题背后其实是在训练你一个底层习惯遇到无序数组求解最值先停下来问自己——能不能排序能排序的话复杂度和思路常常会豁然开朗。再往深一层这道题还暗含了“贪心 窗口”的思想排序后为了让差值最小窗口内必然不包含“多余”的离群元素。这个逻辑和“最小生成树先排序边”“区间调度先按端点排序”是同一个思维模式。如果你能在一道简单题里总结出这种规律那你对题目的理解就已经超过大多数只看过题解的人。6. 个人经验与最后的小建议这道题我大概刷过三遍第一次用暴力组合超时第二次看了题解恍然大悟第三次是在周赛前复习三分钟 AC。每次重刷都能有新的体会。我现在写滑动窗口题时已经养成一个肌肉记忆先判断窗口是否固定再判断需要维护什么然后决定是否需要预处理比如排序、前缀和、单调队列。1984 就是“固定窗口 排序预处理”的完美组合。如果你正在刷 LeetCode 每日一题我特别建议你把这题和 643. 子数组最大平均数 I 放在一起做。643 也是固定窗口但维护的是窗口和思路几乎一模一样。两道题做完你会对固定窗口产生条件反射。再之后可以挑战 239 和 76那才是真正把滑动窗口吃透的分水岭。一个小技巧在本地调试时准备几组特殊用例比如nums [1], k 1返回 0nums [1, 1, 1, 1], k 2返回 0nums [9, 4, 7, 1, 3], k 3手动算一下答案是 4窗口 [1,3,4] 或 [3,4,7] 或 [4,7,9] 里选最小差是 3等等我算一下排序后 [1,3,4,7,9]k3窗口 [1,3,4] 差3[3,4,7] 差4[4,7,9] 差5所以最小是3。每次用这类小用例跑通基本就能保证代码正确。LeetCode 的判题数据很全但如果我们自己多做一步自测提交通过率会更高心态也会更稳。今天这道题就分享到这里。如果你也对每日一题的题解感兴趣不妨关注我的博客或者加个书签我会持续更新一些简单题背后的复杂思维。刷题路上最大的成就感不是 AC 的数量而是把每一道简单题都吃得明明白白。希望这次关于 1984 的拆解能帮你把“排序 滑动窗口”这个组合深深印在脑子里下次遇到类似题目直接条件反射写出最优解。