LC1984. 学生分数的最小差值

题目描述

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。 从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。 返回可能的 最小差值 。

示例 1： 输入：nums = [90], k = 1 输出：0 解释：选出 1 名学生的分数，仅有 1 种方法：

• [90] 最高分和最低分之间的差值是 90 - 90 = 0

可能的最小差值是 0 示例 2： 输入：nums = [9,4,1,7], k = 2 输出：2 解释：选出 2 名学生的分数，有 6 种方法：

• [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
• [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
• [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
• [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
• [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
• [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6

可能的最小差值是 2 提示： 1 <= k <= nums.length <= 1000 0 <= nums[i] <= 10^(5)

题目解析

题目在说什么

想象你是一个老师，班上有好多学生，每个学生有一个分数。现在你想选 恰好 k 个学生 出来，让这组学生里 最高分和最低分的差距 尽可能小。 比如分数是 [9,4,1,7]，你要选 2 个学生，那么所有可能的两人组合里，差距最小的是哪一对？答案是 7 和 9（差距 2），或者 1 和 4（差距 3）…… 最终最小是 2。 如果只选 1 个人，那最高分和最低分就是同一个人，差距是 0。

所以题目就是：给你一堆分数，让你选 k 个，使得这 k 个分数里最大值减最小值的结果最小。

---

思路是怎么来的

生活比喻： 假设你有一堆不同长度的绳子，你想挑出 k 根，让它们长度最接近（也就是最长和最短的差最小）。你会怎么做？ 你会先把所有绳子按长度排好队，从短到长。然后，既然要选 k 根，那最接近的 k 根肯定在排序后的队列里是 连续的一段。 比如绳子长度排好是 [1, 4, 7, 9]，你要选 2 根，那最接近的两根一定是挨着的：1和4差3，4和7差3，7和9差2。你看，连续的两根差距最小是 2。

为什么是连续的？ 因为如果你跳着选，比如选 1 和 9，差距 8 肯定比相邻的大。所以为了最小化差距，你选的 k 个分数在排序后一定是 紧挨着的，这样最高分和最低分才最接近。

核心想法： 1. 先把分数从小到大排序。 2. 然后，用一根“滑动窗口”在排好序的数组上滑动，窗口大小就是 k。 3. 每个窗口里，最高分就是窗口最右边的数，最低分就是最左边的数，差值就是 nums[i+k-1] - nums[i]。 4. 遍历所有可能的窗口，记录最小的那个差值。

---

代码逐步拆解

我们拿示例 2 来走一遍：nums = [9,4,1,7], k = 2

第一步：排序

nums.sort()  # 变成 [1, 4, 7, 9]

排序后，分数从小到大排好，这样相邻的分数差距最小。

第二步：滑动窗口找最小差值 我们需要一个变量记录当前看到的最小差值，一开始设成很大的数，比如 float('inf') 或者直接用 nums[-1] - nums[0]（最大可能差值）。 然后从数组开头开始，每次取连续 k 个数，计算差值，更新最小值。

min_diff = float('inf')  # 先设成无穷大
for i in range(len(nums) - k + 1):  # i 从 0 到 len(nums)-k
    diff = nums[i + k - 1] - nums[i]  # 窗口右端减左端
    min_diff = min(min_diff, diff)    # 更新最小差值

拆解这个循环：

• range(len(nums) - k + 1)：因为窗口大小是 k，最后一个窗口的起始位置是 len(nums)-k，比如这里 len=4, k=2，起始位置可以是 0,1,2（一共 3 个窗口）。
• 当 i=0：窗口是 [1,4]，差值 = 4-1 = 3，min_diff 变成 3
• 当 i=1：窗口是 [4,7]，差值 = 7-4 = 3，min_diff 还是 3
• 当 i=2：窗口是 [7,9]，差值 = 9-7 = 2，min_diff 更新为 2

循环结束，min_diff 就是 2。

完整代码：

class Solution: