LeetCode 1984. Minimum Difference Between Highest and Lowest of K Scores
题目描述
给你一个下标从 0 开始的整数数组 nums，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k。
从数组中任意挑选 k 名学生的分数，使这 k 个分数中最高和最低分数的差值最小化。
返回最小可能的差值。
示例
示例 1：
输入：nums = [90], k = 1 输出：0 解释：只有一种方式选择一名学生的分数：[90]。最高分与最低分的差是 90 - 90 = 0。最小可能差值为 0。
示例 2：
输入：nums = [9,4,1,7], k = 2 输出：2 解释：有多种方式选择两名学生的分数。例如选择 [9, 7]，差值为 9 - 7 = 2。最小可能差值为 2。
约束条件
1 <= k <= nums.length <= 10000 <= nums[i] <= 10^5
解题思路
为了最小化选出的 k 个元素中最大值与最小值的差值，最优策略是将数组排序。排序后，任意 k 个连续的元素构成的子数组，其最大值与最小值的差即为该子数组首尾元素的差。
因此，只需遍历所有长度为 k 的连续子数组，计算 nums[i + k - 1] - nums[i] 的最小值即可。
代码实现
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
nums.sort()
res = float("inf")
for i in range(len(nums) - k + 1):
res = min(res, nums[i + k - 1] - nums[i])
return res