LeetCode1984. 学生分数的最小差值（打卡Java版）

曾经终败给现在 2023-10-01 17:55 4阅读 0赞

### 1984. 学生分数的最小差值（简单） ###

这题太简单了，纯打卡记录，几乎没有阅读价值。

给你一个 **下标从 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

### 思路 ###

想最小化选择的 `k` 名学生中最高分和最低分的差值，我们可以在排好序后的数组中连续地进行选择。

这样一来，我们首先对数组nums 进行`升序排序`，随后使用一个大小固定为 `k` 的`滑动窗口`在 nums 上进行遍历。记滑动窗口的左边界为 i，那么右边界即为 i+k-1，窗口中的 k 名学生最高分和最低分的差值即为 nums\[i+k-1\] - nums\[i\]。

最终的答案即为所有 nums\[i+k-1\] - nums\[i\]中的最小值。

### 代码 ###

class Solution {
        
        /**
         * 方法：排序 + 滑动窗口
         * 时间复杂度：O(nlogn)，排序O(nlogn)，遍历O(n)
         * 空间复杂度：O(logn)，排序时使用的栈空间
         */
        public int minimumDifference(int[] nums, int k) {
        
            if (null == nums || nums.length <= 1 || k < 1 || k > nums.length) {
        
                return 0;
            }
            // 排序
            Arrays.sort(nums);
            int len = nums.length;
            int ans = Integer.MAX_VALUE;
            // 滑动窗口
            for (int i = 0; i < len - k + 1; i++) {
        
                ans = Math.min(nums[i + k - 1] - nums[i], ans);
            }
            return ans;
        }
    }