1984. 学生分数的最小差值

• 标签：数组、排序、滑动窗口
• 难度：简单

题目链接

• 1984. 学生分数的最小差值 - 力扣

题目大意

描述：给定一个下标从 $0$ 开始的整数数组 $nums$，其中 $nums[i]$ 表示第 $i$ 名学生的分数。另给定一个整数 $k$。

要求：从数组中选出任意 $k$ 名学生的分数，使这 $k$ 个分数间最高分和最低分的差值达到最小化。返回可能的最小差值 。

说明：

• $1 \le k \le nums.length \le 1000$。
• $0 \le nums[i] \le 10^5$。

示例：

• 示例 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$ 名学生中最高分与最低分的差值，我们应该在排序后的数组中连续选择 $k$ 名学生。这是因为如果将连续 $k$ 名学生中的某位学生替换成不连续的学生，其最高分 / 最低分一定会发生变化，并且一定会使最高分变得最高 / 最低分变得最低。从而导致差值增大。

因此，最优方案一定是在排序后的数组中连续选择 $k$ 名学生中的所有情况中的其中一种。

这样，我们可以先对数组 $nums$ 进行升序排序。然后使用一个固定长度为 $k$ 的滑动窗口计算连续选择 $k$ 名学生的最高分与最低分的差值。并记录下最小的差值 $ans$，最后作为答案并返回结果。

思路 1：代码

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = float('inf')
        for i in range(k - 1, len(nums)):
            ans = min(ans, nums[i] - nums[i - k + 1])

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log n)$，其中 $n$ 为数组 $nums$ 的长度。
• 空间复杂度：$O(1)$。

思路 2：

思路 2：代码

思路 2：复杂度分析

• 时间复杂度：
• 空间复杂度：