大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

从数组中任意挑选 k 个数字，让这 k 个数字的 最大值 - 最小值 的结果最小。

解题方法

以 nums = [9,4,1,7], k = 2 为例，我们看到当挑选 [9, 7]这两个数字的时候，两个数字的差是 2，这个差是最小的。你无论挑选另外的哪两个数字，差都比 2 大。

怎么寻找 k 个数字的最大值和最小值的差呢？这让我们想到，对数组进行排序，然后利用大小为 k 的滑动窗口遍历整个数组。滑动窗口最右边的值就是窗口内的最大值，滑动窗口最左边的值就是窗口内的最小值。

因此，我们要寻找的就是已经排序的数组中，所有大小为 k 的滑动窗口中，最右端数字 - 最左端数字 的最小结果。

1984. 学生分数的最小差值.001.png

  1. class Solution {
  2. public:
  3.     int minimumDifference(vector<int>& nums, int k) {
  4.         sort(nums.begin(), nums.end());
  5.         int res = INT_MAX;
  6.         for (int i = 0; i <= nums.size() - k; ++i) {
  7.             res = min(res, nums[i + k - 1] - nums[i]);
  8.         }
  9.         return res;
  10.     }
  11. };
  • 时间复杂度：$O(N*log(N))$，N 是数组的长度。
  • 空间复杂度：$O(1)$。

总结

  1. 对于 Easy 题目，写法一般不难。重点是对题目的抽象上。
  2. 注意一下滑动窗口的边界，不要超过数组范围。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。