很多刷算法的朋友第一次看到 排序(类似滑动窗口) 这个标签组合多少会有点疑惑这题的 k 个分数是随便从数组里挑的又不是原数组中连续的一段凭什么说它是滑动窗口又为什么非得排序今天就拿 LeetCode 1984 当引子把排序 固定宽度窗口这类题型的来龙去脉一次讲透顺带把代码细节和踩坑点都过一遍。这道题的题面很直白给你一个整数数组 nums里面存的是学生分数再给一个整数 k要求从数组里任选 k 个分数让这 k 个分数里的最大值和最小值的差尽可能小返回这个最小差值。适合正在刷题准备面试、或者刚接触先排序再扫描这类套路的朋友。看完这篇你会明白为什么排序在这个问题里是绕不开的关键步骤也会清楚类似滑动窗口到底是指什么以及类似的题以后要怎么下手。1. 题目在考什么从题意到思维模型1.1 一句话还原题目场景先把英文题面翻译成大白话。假设一个班有 n 个学生分数放在数组 nums 里老师想挑 k 个学生出来组成小组希望这个小组里最高分和最低分的差距尽量小。比如nums [9, 4, 1, 7], k 2四个分数里任意挑两个差值最小的组合是 7 和 9差值是 2所以答案是 2。注意这里有一个核心约束k 个元素不是连续的一段也没有要求你按什么顺序挑。这就是题目第一个陷阱——很多人第一反应是那我找出原数组里相邻元素的最小差值不就行了但题目根本不要求下标连续。正因为如此才需要额外的一步处理把任意挑选转换成可扫描的形式这个转换工具就是排序。还有几个边界条件值得一开始就留意k 可以等于 1也可以等于整个数组长度。这两种情况其实对应了题目的两个极端后面在代码部分会专门处理。1.2 题目真正的考点在哪里LeetCode 给这题贴的标签是 Array、Sorting、Sliding Window。很多人看到 Sliding Window 就条件反射地去找滑动窗口模板比如维护左右指针、动态伸缩窗口之类的但这题其实挺反套路的它虽然叫滑动窗口却不需要任何动态维护的操作因为排序完成后窗口内最大值就是右端元素、最小值就是左端元素差值就是nums[right] - nums[left]根本不需要维护窗口内最大最小值的数据结构。所以这道题真正在考的是三件事能不能看出任意选 k 个和排序后连续取 k 个是等价的——这是整个解题思路的命门。能不能正确实现固定宽度窗口的遍历边界——代码很简单但边界写错的人真不少。能不能说清楚复杂度——排序是 O(n log n)扫描是 O(n)总复杂度就是 O(n log n)n 最大 1000完全无压力。这题是 Easy 难度但它的思维分量不低。很多中等难度的题比如后面要提到的最小化数组中配对的最大差值本质上都共享同一个前置结论排序之后极差最小的一组数一定落在某个连续区间里。2. 为什么排序之后用固定窗口就能得到答案2.1 暴力解法先看看上限在哪在没有思路之前先想一下暴力怎么做。最朴素的办法就是枚举所有 C(n, k) 种组合每组算一个最大值减最小值取全局最小。当 n 1000、k 500 的时候C(1000, 500) 这个数字你甚至没法想象它超过了 10^299算到宇宙毁灭都跑不完。所以暴力只适用于 n 很小比如 n ≤ 15的场景在这个题的数据范围下必须另找出路。另一种不太暴力的思路是枚举所有可能的最大值下标 i 和最小值下标 j然后检查数组中处于nums[i]和nums[j]之间的元素够不够 k 个。这样做是 O(n²) 级别的而且实现起来比排序方案复杂得多。无论哪种暴力最后都指向一个结论你需要某种全局有序的结构才能避免对每个组合分别算差值。2.2 一个身高排序的类比为什么排序后取连续 k 个就是最优的这里用一个特别生活的例子解释。想象班里所有人按身高从矮到高排成一列你被要求从队列里挑 k 个人让最高和最矮的身高差最小。你会怎么挑几乎一定是挑挨在一起的 k 个。为什么因为如果你跳过了队伍中间的某个人而去挑了更后面的高个子那你的身高差只会变大或不变不可能变小。这个道理放到分数上完全一样。排序之后如果你挑的 k 个人在队伍里不是连续的比如下标是 1、2、5那你完全可以把 5 换成 4 或者 3因为中间的分数比 5 小但比 2 大换完之后最大值变小了差值只会更小。反复做这样的收缩最终一定可以收缩成一段连续的下标区间。这个直觉就是整道题的核心。2.3 数学上的简洁证明直觉聊完了还是要给一个能写在面试题解里的严谨版本。假设排序后的数组为a[0] ≤ a[1] ≤ ... ≤ a[n-1]任意选出 k 个元素它们在排序数组中的下标记作i1 i2 ... ik。因为这 k 个下标各不相同所以最后一个下标ik和第一个下标i1之间至少隔了 k-1 个位置也就是ik - i1 ≥ k - 1现在把目光移到连续窗口a[i1], a[i11], ..., a[i1k-1]。因为i1k-1 ≤ ik而数组已经有序所以a[i1k-1] - a[i1] ≤ a[ik] - a[i1]右边a[ik] - a[i1]正是原来那组任意选择的差值左边是某个固定宽度为 k 的连续窗口的差值。这个式子说明任意一组选择的差值都不小于某个包含它左端点的连续窗口的差值。换句话说全局最优解一定藏在某个固定宽度为 k 的连续窗口里。于是问题从任选 k 个元素退化成了在有序数组中扫一遍所有宽度为 k 的窗口求首尾差的最小值。2.4 这道题为什么只是类似滑动窗口既然叫滑动窗口那就得说清楚它和真正的滑动窗口模板之间的区别。标准的滑动窗口题比如无重复字符的最长子串或者长度最小的子数组有两个典型特征第一处理的必须是原数组中连续的一段第二窗口需要根据条件动态扩张或收缩所以你得在循环里用 while 控制左指针。这道题不一样。排序之后窗口虽然也是连续的一段但这个连续是值域上的连续不是原数组下标上的连续。更关键的是窗口宽度固定为 k扫描时左右指针一起向右移动不需要判断什么时候扩张、什么时候收缩。你只需要算a[ik-1] - a[i]就行了。所以准确的说法是我们先借排序把任意挑选等价变形为有序数组中的连续段再借滑动窗口的遍历方式来枚举所有可能的情况。它用了滑动窗口的形却没有滑动窗口的神这就是标题里类似两个字的由来。面试时如果能把这个区别说出来比直接报出代码要加分得多。3. 代码落地Python和Java双版本3.1 Python实现与逐行拆解下面给出 Python 版本我习惯把边界条件写清楚避免歧义from typing import List def minimumDifference(nums: List[int], k: int) - int: if k 1: return 0 nums.sort() n len(nums) ans float(inf) for i in range(n - k 1): diff nums[i k - 1] - nums[i] if diff ans: ans diff return ans逐行说几个关键点if k 1: return 0。只选一个分数时最大值和最小值都是它自己差值必然是 0不用进循环。nums.sort()。Python 里nums.sort()是原地排序不产生新列表如果你写sorted(nums)会返回新列表刷题时原地排序更省内存。for i in range(n - k 1)。这是固定窗口的遍历方式i 是窗口左端点。当i n-k时窗口右端点是n-1刚好覆盖到数组末尾。nums[i k - 1] - nums[i]。ik-1是右端点下标注意这里要减 1。很多人写成nums[ik]导致窗口实际宽度变成 k1甚至数组越界。3.2 Java实现与细节差异Java 版本几乎一模一样差别只在语法层面import java.util.Arrays; class Solution { public int minimumDifference(int[] nums, int k) { if (k 1) { return 0; } Arrays.sort(nums); int n nums.length; int ans Integer.MAX_VALUE; for (int i 0; i k - 1 n; i) { ans Math.min(ans, nums[i k - 1] - nums[i]); } return ans; } }两个版本对比有几点需要展开说Arrays.sort用的是双轴快速排序对int[]是原地排序额外空间 O(log n)递归栈。面试官如果追问你可以提到对于引用类型数组如Integer[]Java 会改用 TimSort此时要求对象实现Comparable或者传入Comparator。循环条件写成i k - 1 n比i n - k 1更不容易出错。两者等价但前者的语义直接和右端点绑定我看到很多人写后者的时候容易把1或-1弄反。初始化ans Integer.MAX_VALUE。理论上把ans初始化为nums[n-1] - nums[0]也正确因为真实答案一定不会超过这个值但用 MAX_VALUE 可以形成统一习惯以后遇到更复杂的题也不容易翻车。3.3 时间复杂度和空间复杂度怎么算排序是O(n log n)。固定窗口扫描是O(n)因为循环只会执行n-k1次最多不超过 n 次。总时间复杂度就是O(n log n)这也是本题最优复杂度。空间复杂度Python 的list.sort()是原地排序额外空间主要是 TimSort 的临时数组可以粗略认为是O(n)Java 的Arrays.sort对基本类型数组是原地排序额外空间约O(log n)。如果强行要一个统一的说法就写原地排序额外空间视语言和排序实现为 O(n) 或 O(log n)。值得一提的是题目给的n ≤ 1000就算你用O(n²)的暴力也未必超时但 LeetCode 的价值从来不只是跑过样例而是让你在更大数据范围下依旧给出干净的解法。把排序的 O(n log n) 这个复杂度记牢后面遇到n 10^5甚至更大的同类题时你会有明确的优化方向。4. 实战中容易翻车的几个细节4.1 窗口索引边界ik 还是 ik-1这是我见过翻车率最高的地方。假设k 2窗口里应该有两个元素左端nums[i]右端nums[i1]。而i1 ik-1所以正确写法是nums[ik-1]。如果你写nums[ik]当i n-2时ik n直接越界。记住一个口诀窗口宽度是 k右端下标是左端加宽度减一。这看起来是小学算术但人在紧张写题的时候就是会错。建议写完代码立刻用n4, k2这种小样例手推一遍i0对应下标 0 和 1i1对应 1 和 2i2对应 2 和 3。推完就不会错了。4.2 排序前别急着开窗另一个常见的错误是不排序直接套窗口。有人觉得滑动窗口不是处理原数组的连续段吗那我把原数组的连续 k 个算一遍不就行了这就是对题目性质理解偏差。题目选 k 个分数根本不要求原数组下标连续所以原数组相邻元素之间没有任何差值最小化的约定。举个反例nums [100, 0, 50, 1], k 2原数组相邻差是 100、50、49最小是 49但正确答案显然应该选 0 和 1差值是 1。只有排序后50 和 100、0 和 1 这类值域相近的元素才会聚到一起窗口才真正有意义。所以我在刷题时会给自己一个强制提醒凡是选 k 个元素 极差/极值和最小化的题第一步永远是问自己——排序之后这个问题会变成什么很多时候答案就是连续段的某个值。4.3 重复分数和 k1 的边界处理如果分数里有大量重复值比如nums [3, 3, 3, 5], k 3排序后窗口[3, 3, 3]的差值是 0答案就是 0。这种用例能顺利跑过因为固定窗口扫描会自然地捕捉到重复元素聚在一起的情况。但要注意如果k 1任一窗口都是单个元素差值恒为 0这时候如果你不做提前返回走进循环也没问题——diff会算出来 0 并更新ans。所以提前返回只是一个意图清晰化的小优化不是必须的。不过我还是强烈建议把if (k 1) return 0写上原因有二第一它让代码的意图更明确读者一看就知道单个分数的差值必然是 0第二它在语义上和其他边界条件比如k n形成对照暴露你对题目的理解是完整的。4.4 一个可能的短路优化在固定窗口扫描过程中一旦发现ans 0就可以直接退出循环。因为差值不可能小于 0此时已经找到全局最优。对这道题来说n最多 1000这个优化聊胜于无但它是一个很好的习惯——在更大的数据范围里剪枝往往能省掉大量无用遍历。for i in range(n - k 1): diff nums[i k - 1] - nums[i] if diff 0: return 0 ans min(ans, diff)当然这种提前返回要建立在你确定0是理论下界的基础上。差值从来都是非负的所以这里是安全的。5. 这个套路能迁移到哪些题目上5.1 极差最小化题型的通用思考路径这题的解题链条可以扩展成一个通用模板看到任选 k 个元素先别急着动态规划或贪心试试排序。排序后把问题改写成有序数组上找一个连续段通常问题会瞬间简化。用固定宽度的窗口或者双指针去扫描这一段维护你需要的那个指标。必要时在扫描中做剪枝优化比如最小值 0 或者某个上界。举个例子LeetCode 2616 要求把数组里的数字两两配对最小化所有配对中差值较大的那一对约束是只能选不相邻的配对等等。那题的经典解法也逃不开先排序然后二分答案再用贪心检查和配对是否足够。你看第一步还是排序。还有一道很经典的 LeetCode 910最小差值 II给每个数加上或减去 k让最终数组最大值和最小值之差最小。它同样先排序然后枚举转折点左边都加 k右边都减 k依然是用排序把任意元素的位置关系变成有序的相邻关系。5.2 与真正的滑动窗口题如何区分很多人混淆扫描有序数组的固定窗口和真正意义上的滑动窗口。我自己的判断标准很简单如果窗口的左右指针需要根据某个动态条件分别移动比如和小于 target 就扩右大于就缩左那是标准滑动窗口如果窗口宽度固定只是从左到右平移那本质上就是一次普通的线性扫描顶多叫固定窗口滑动如果窗口内要维护的东西需要特殊数据结构比如最大/最小值那就要上单调队列了。拿 LeetCode 239滑动窗口最大值来对比最合适。那道题的窗口在原数组上滑窗口里的最大值会随着右端进入、左端离开而动态变化所以必须用单调队列维护。而本题排序后窗口的最大值和最小值永远在两端完全不需要维护直接取首尾即可。这就是类似滑动窗口和真滑动窗口之间最直观的分界线。5.3 相关题目的延伸顺着这个思路往下走有几道题值得作为课后练习LeetCode 1508排序后维护前缀和和连续段思维有关。LeetCode 2616排序 二分答案经典中的经典。LeetCode 910排序 单点枚举。如果面试中你拿到一道选 k 个元素最小化极差的题能在一分钟内说出先排序再滑一个固定 k 的窗口面试官基本就会点头了如果你还能补充为什么排序后连续 k 个就是最优的那个证明那这一题在算法能力上的分数就拿到了。最后分享一个刷题之外的心得。LeetCode 1984 这类 Easy 题看起来人畜无害但它其实是很多排序预处理思想的启蒙题。我见过不少同学一上来就背各种复杂模板反而把最简单有效的排序手段丢在一边。其实刷题不需要追求每道题都做得多炫技把排序 扫描用到肌肉记忆里很多中难题的第一步就迈出去了。动手把这题的两个语言版本都敲一遍再用n4, k3之类的边界数据自己走一遍循环比看十遍题解都管用。