排序是这个题最自然的出发点但真正值得琢磨的是后面那一层把连续子数组的跨度当成候选答案这其实就是滑动窗口的雏形。这篇我就以 LeetCode 1984 题为引子把从读题到 AC 再到举一反三的全过程拆开讲一遍既有代码也有踩坑记录顺手解决“为什么排序之后只需要看相邻窗口”这个很多人第一次没想明白的点。1. 读懂题目从描述到公式化表达1.1 题面还原与通俗解读先看原题给你一个下标从 0 开始的整数数组nums其中nums[i]表示第 i 名学生的分数另给你一个整数k。你需要从数组中选出任意 k 名学生的分数让这 k 个分数里最高分和最低分的差值尽可能小最后返回这个最小的可能差值。举个例子输入nums [9, 4, 1, 7], k 2 输出2 解释选出 [9, 7]最高分 9最低分 7差值为 2为什么不是选[1, 7]因为差值是 6。所有两两组合里[7, 9]的差值 2 最小。如果k 3同样的数组最合适的组合是[4, 7, 9]差值 9 - 4 5。这道题在 LeetCode 上的编号是 1984难度属于 Easy但用一句话概括它的本质在一维数组中挑固定数量元素要求选中集合的数值跨度最小。1.2 为什么这道题值得单独记录很多人看到 Easy 就直接跳过其实这道题至少有三个值得练的点它是“排序 滑动窗口”这一类问题里最干净的入门样本。没有复杂的数据结构没有特殊边界所有逻辑都集中在“为什么排序后只需检查相邻窗口”这个直觉上。它能把“暴力枚举”到“线性扫描”的优化路径讲透。先写一个三重循环的解法再写成 O(n log n) 的排序加 O(n) 的扫描这个过程比单纯背模板有价值得多。它是很多“k 个元素最小跨度类”题目的母板。后面遇到的“最接近的三数之和”“子数组最大平均值”等题目核心骨架都是这个思路的延伸。所以我建议刷题记录里不要只记 Hard 题像这种 Easy 题反而是把基础概念钉牢的最佳素材。1.3 一个真实的场景类比如果把题目翻译成现实场景大概是这样期末成绩出来了老师想从全班 40 个人里挑出 k 5 个人组成一个学习小组要求这 5 个人水平最接近方便统一辅导方案。这时候你第一反应是什么是先把分数从低到高排好然后看哪 5 个相邻位置上的人总分跨度最小。我们不会去枚举所有 C(40, 5) 种组合而是先排序因为“水平接近”在分数轴上的表现必定是聚在一起的。这就是本题的全部直觉。2. 思路拆解为什么排序后只需检查相邻窗口2.1 暴力做法的成本先看最朴素的做法枚举所有长度为 k 的组合对每个组合找出最大值和最小值计算差值保留全局最小值。假设数组长度是 n那么组合数量是 C(n, k)。当 n 1000、k 50 时这个组合数是天文数字。即便用递归剪枝也不可能在合理时间内跑完。所以暴力只能用来验算小数据不能作为正式解法。这里有个容易被忽略的点对于每个组合“求最大值和最小值”如果每次都用max()和min()那又引入 O(k) 的额外开销。整体复杂度会变成 O(C(n, k) * k)比看起来还要糟。2.2 排序让问题降维现在换一个角度。如果先把数组排好序那么“任意 k 个元素的最高分与最低分”会有什么变化排序后数组是单调递增的比如[1, 4, 7, 9]。当我们从中取 k 个元素时如果这 k 个元素的最高分是nums[j]、最低分是nums[i]其中i j那么它们之间的所有元素都在区间[nums[i], nums[j]]内。这个跨度nums[j] - nums[i]本质上就是排序后数组上某两个端点之间的区间长度。关键洞察是如果存在一个最优解选择的 k 个元素在排序后并不连续即中间隔着未选中的元素那么我们一定可以把窗口往中间收缩把未选中的元素替换成更靠近端点的元素从而让跨度变得更小或保持不变。这就是“排序后只需检查连续子数组”的原因。严格证明可以用反证法假设最优解选了排序后下标i1 i2 ... ik且存在某个t使得i_{t1} - i_t 1即中间有空隙。那么我们把i_{t1}换成i_t 1新的集合中最大值不会变大因为替换进来的元素更小最小值不会变小因为只是替换中间元素跨度不可能变大。重复这样的替换最终可以得到一个连续的区间其跨度不大于原最优解。因此检查所有长度 k 的连续子数组就足够了。2.3 滑窗的直观操作有了排序做前提剩下的操作就很简单排序数组复杂度 O(n log n)用左右指针维护一个长度为 k 的窗口初始时left 0right k - 1计算nums[right] - nums[left]窗口右移一格即left 1right 1继续计算直到right走到数组末尾所有差值里取最小值为什么窗口每次只移动一格因为排序后跨度只可能随着端点变化而变化。如果我们跳过某个位置反而可能漏掉最优解。窗口逐个滑动就等价于枚举了所有开头位置这种扫描方式和求连续子数组最大和里的滑窗逻辑完全一致。2.4 复杂度分析时间复杂度排序 O(n log n)一趟扫描 O(n)总复杂度 O(n log n)空间复杂度排序通常用 O(log n) 的栈空间语言自带排序实现否则只用 O(1) 额外变量如果你用的是 Java 的Arrays.sort或 Python 的sorted基础类型排序是双轴快排/归并排序空间复杂度可以按 O(log n) 估算。3. 实现落地Python 逐行拆解与变体写法3.1 标准写法def minimumDifference(nums, k): if k 1: return 0 nums.sort() ans float(inf) n len(nums) for i in range(n - k 1): window_diff nums[i k - 1] - nums[i] if window_diff ans: ans window_diff return ans这段代码就是本题的标准答案。不过逐行拆开看有几个细节值得留意k 1是特判。因为只选一个学生最高分和最低分是同一个数差值必然是 0。range(n - k 1)确保了i k - 1不会越界。当i n - k时右端点是n - 1正好是数组最后一个元素。float(inf)用来初始化最小值避免用nums[-1] - nums[0]这种“看起来合理但可能不是答案”的值污染比较逻辑。3.2 用双指针风格改写有些读者对“窗口”的理解更偏向指针移动那可以写成这样def minimumDifference(nums, k): if k 1: return 0 nums.sort() left 0 ans float(inf) for right in range(k - 1, len(nums)): ans min(ans, nums[right] - nums[left]) left 1 return ans这次right从k - 1开始每次循环自然形成一个[left, right]的窗口计算完之后left和right同步右移。这段代码的可读性比第一种更好尤其在面试里写白板的时候能边说边写。3.3 负数与重复分数的情况思考一个边界分数数组里可能出现负数吗原题说是分数现实中分数一般非负但 LeetCode 的测试用例里并不保证“分数”必须是 0 到 100 的整数它本质上就是整数数组。排序对负数同样适用nums[right] - nums[left]的结果可能是负数吗不会因为排序后nums[right] nums[left]差值一定非负。但如果数组里有重复分数比如[80, 80, 85]排序后窗口差值可能为 0这是合法答案不能因为“看着像没处理”就排除。3.4 如果要求在原数组上操作有些语言或场景不允许排序后修改原数组比如后面还要用原始顺序那就需要复制一份nums_copy sorted(nums)代价是额外 O(n) 空间时间复杂度不变。在实际工程里是否允许原地排序取决于数据结构是否还有别的使用者在面试里最好主动问一句“可以修改原数组吗”这会让面试官觉得你考虑事情周全。4. 从 AC 到举一反三这类题还能怎么考4.1 把 k 固定改为不定区间如果题目变成“选出任意数量学生要求分数跨度小于等于某个阈值求最多能选几个人”那就变成“最长连续子数组”问题。思路依然是排序 双指针尺取法只是滑动窗口的长度不再固定而是根据nums[right] - nums[left]动态调整。这也是一个经典变体做完 1984 之后可以顺手练一练“最长连续非递减子数组”之类的问题逻辑链条基本是相通的。4.2 把最大值和最小值的差值改为最小化方差如果再进一步要求“使这 k 个数的方差最小”排序的思路是否还成立答案是依然成立因为方差衡量的是数据集中程度数据越集中方差越小。排序后连续 k 个数已经是“局部最集中”的候选只是计算方差要比计算跨度多一层求和同平方复杂度变成 O(n log n n*k)还可以用前缀和优化成 O(n log n n)。4.3 与分组问题的结合另一种考法把数组分成若干组每组恰好 k 个学生要求所有组内差值之和最小。这就需要先把数组排序然后做动态规划。虽然题目难度上了一个台阶但第一步“排序让同类聚在一起”的思路和 1984 完全一致。做题最爽的瞬间就是发现新题里藏着旧题的内核。4.4 数据结构升级版如果数组会动态修改插入、删除、修改分数同时频繁查询“当前数组里选 k 个学生的最小差值”排序就不能每次重来。这时候可以用有序集合如平衡树维护一个滑窗新增元素 O(log n)删除元素 O(log n)每次查询窗口内最大值和最小值的差值 O(1)。这已经是竞赛级别的内容了但理解这个升级路径能帮你把简单题的价值榨干。5. 常见错误与排查实录5.1 忘记处理 k 1这个错误出现频率极高。很多人写完主逻辑直接提交遇到nums [1], k 1用例就挂了。为什么因为窗口扫描时range(n - k 1)得到range(1)循环一次nums[0] - nums[0] 0理论上结果也算得出来。但如果数组长度是 1n - k 1是 1循环没问题如果数组长度很长且 k 1循环会执行 n 次每次都计算nums[i] - nums[i] 0最终答案也是 0不会出错。那为什么还要特判为了效率。k 1 时答案必然为 0提前返回能省掉整个排序和扫描过程。这个特判算是一种优化面试时提出来属于“这个小细节我也注意到了”的加分项。5.2 窗口右端点越界写循环时如果直接写for i in range(n):然后内部用nums[i k - 1]当i接近n时会数组越界。正确的循环上界是n - k 1。排查方法很简单在循环体开头打印i和i k - 1肉眼就能看出问题。5.3 初始化 ans 为nums[-1] - nums[0]有人觉得反正答案是某个窗口差值不如先算第一个窗口作为初始值。这样写本身没有逻辑错误但容易踩一个隐藏坑如果nums还没排序nums[-1] - nums[0]可能是负数后面比较时所有正差值都比这个“假最小值”大导致结果恒为一个负数直接 WA。要避免它最稳的办法就是float(inf)初始化省心。5.4 没有理解“为什么窗口必须连续”这是最常见的心态问题。很多人看完题解会有一个疑问排序后我随便挑 k 个不连续的元素比如下标[0, 2, 4]跨度也未必比连续窗口[0, 1, 2]大啊为什么一定能保证最优解在连续窗口里这个问题其实我在第 2.2 节已经用反证法解释过。这里再用一个直观例子补一刀数组[1, 2, 100, 101]k 2。选[1, 101]跨度 100选[2, 100]跨度 98但最优解显然是[1, 2]跨度为 1。不连续的组合跨度要么更大要么在替换后能变得更小继续替换直到连续。所以连续窗口不会漏解这也是整个算法成立的地基。5.5 排序稳定性会影响结果吗不会。因为我们只关心端点差值不关心相同值的内部顺序。nums.sort()用稳定排序也好不稳定排序也罢[5, 5]的窗口差值都是 0。如果你非要较真可以看看 Java 里Arrays.sort对对象数组用归并排序对基础类型用双轴快排但放到这个题目里结果完全相同。5.6 大数据量下超时排查如果提交时超时八成是你用了暴力枚举。解决方法是换排序 滑窗时间复杂度直接从指数级降到 O(n log n)。还有一个隐性坑在循环里频繁调用len(nums)其实没关系Python 的len()是 O(1) 操作但如果你写成for i in range(len(nums))并在循环体里修改nums那才真正会出问题。本题不涉及修改数组所以放心用。6. 写在最后的实操心得我个人刷这道题的体会是它表面上是一道“数组处理题”实际上是“排序让无序问题变有序”这个思维模式的速成课。很多初学者拿到题目会本能地去模拟“选 k 个人”这个动作但一旦意识到排序后所有候选答案都藏在连续窗口里整个问题就从组合数学变成了线性扫描这种降维打击的快感是刷题最上头的部分。另外一个小建议做完这题可以自己在本地把三种写法都敲一遍——暴力递归版数据量小验证用、排序滑窗版标准提交用、双指针版面试手写用。不要直接复制标准答案因为手敲一遍和看一遍完全是两种吸收率。如果你是在准备面试这道题可以作为“数组 滑动窗口”专题的起手式后面再练 3 道同类型题比如 643 题子数组最大平均数、1004 题最大连续 1 的个数 III、209 题长度最小的子数组基本就能把滑窗的套路记牢了。刷题不是比数量把一道 Easy 题吃透到能给别人讲明白的程度比潦草刷十道 Hard 更有价值。