题目

类型：数组

解题思路

从 n 个元素里找 k 个，使得 k 个元素最大差值最小。

最大值最小化问题容易想到「二分」，利用答案本身具有「二段性」，来将原本的求解问题转化为判断定问题。

回到本题，容易证明，这 k 个元素必然是有序数组中（排序后）的连续段。
反证法，若最佳 k 个选择不是连续段，能够调整为连续段，结果不会变差。

因此我们可以先对 nums 进行排序，然后扫描所有大小为 k 的窗口，直接找到答案，而无须使用「二分」。

代码

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans;
    }
}