学生分数的最小差值

标签: 数组 排序 滑动窗口

难度: Easy

给你一个 下标从 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] <= 105

Submission

运行时间: 29 ms

内存: 16.1 MB

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
       
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 如果k为1，则任何选择都只有一个分数，差值为0
        if k == 1:
            return 0

        # 对分数进行排序
        nums.sort()

        # 初始化最小差值为最大整数
        min_diff = float('inf')

        # 遍历数组，找出连续k个分数的最小差值
        for i in range(len(nums) - k + 1):
            diff = nums[i + k - 1] - nums[i]
            min_diff = min(min_diff, diff)

        return min_diff

Explain

该题解通过先对数组进行排序，然后滑动窗口的方式找出连续k个元素的最小差值来取得解。首先，对于k=1的情况，直接返回0，因为单个元素的最大值和最小值相等。排序后，使用长度为k的滑动窗口遍历数组，计算每个窗口内的最大值与最小值的差值，并更新最小差值。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        # 特殊情况：只选一个学生，差值为0
        if k == 1:
            return 0

        # 对学生分数进行排序
        nums.sort()

        # 初始化最小差值为正无穷，用来记录遍历过程中的最小差值
        min_diff = float('inf')

        # 使用滑动窗口遍历排序后的分数列表
        for i in range(len(nums) - k + 1):
            # 计算当前窗口的最高分和最低分的差值
            diff = nums[i + k - 1] - nums[i]
            # 更新最小差值
            min_diff = min(min_diff, diff)

        # 返回最小差值
        return min_diff

Explore

滑动窗口方法在这个问题中非常有效，因为它允许我们在已排序的数组中连续且高效地检查每个长度为k的子数组。通过排序，数组中的元素按升序排列，因此任何相邻的k个元素都将是可能的最小或最大值的候选者。滑动窗口通过在数组中从左到右移动，每次仅需进行少量计算（比如增加一个元素和移除一个元素的操作），来更新当前窗口内的最大值和最小值的差异，从而找到所有可能窗口中的最小差值。这种方法避免了对每个子数组进行重复全面计算，提高了效率。

排序确实会改变元素的原始顺序，但这对本题的解决不会有影响。题目的目标是找到任意k个学生分数中的最小差值，而不是找到特定顺序学生的差值。排序后，我们更容易直接比较和计算任何连续k个数的差值，因此这种顺序的改变是解题过程中必要和合理的。

若k大于数组长度，理论上无法选择k个学生，因此题目参数应视为无效或题目应当有明确说明处理这种情况。如果没有明确说明，则可以假设返回一个错误消息或特定值（如-1）表示无法选择k个学生。在实际编程实践中，应该对输入参数进行校验，确保k不会超过数组的长度。

在已排序的数组中，滑动窗口的最大值和最小值计算非常高效，因为最小值始终是窗口的第一个元素，而最大值是窗口的最后一个元素。因此，每次窗口滑动时，我们只需要检查新进入窗口的元素和离开窗口的元素，就可以迅速更新差值。如果在未排序的情况下使用滑动窗口，可以通过数据结构如双端队列（Dequeue）来优化最大值和最小值的查找，队列中存储元素的索引，并保持队列的元素值从头到尾是递增（或递减）的，这样队首就是最小值，队尾是最大值。