LeetCode 1984. 最小化 K 个分数的最高与最低分差值

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 <= 1000
• 0 <= 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

复杂度分析

• 时间复杂度：O(n log n)，主要消耗在排序上。