排序 + 滑动窗口

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

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

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

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

代码（二分答案代码见 $P2$）：

###Java

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;
    }
}

###Java

class Solution {
    int[] nums; int k;
    public int minimumDifference(int[] _nums, int _k) {
        nums = _nums; k = _k;
        Arrays.sort(nums);
        int l = 0, r = 100010;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
    boolean check(int x) {
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n && ans > x; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans <= x;
    }
}

• 时间复杂度：排序复杂度为 $O(n\log{n})$；遍历得到答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(\log{n})$

其他「滑动窗口」内容

题太简单？来看一道 更贴合笔试/面试的滑动窗口综合题 🎉 🎉

或是加练其他「滑动窗口」内容 🍭🍭🍭

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

基本分析 & 证明

直觉上，我们会认为「尽量让“较小数”和“较大数”组成数对，可以有效避免出现“较大数成对”的现象」。

我们来证明一下该猜想是否成立。

假定 $nums$ 本身有序，由于我们要将 $nums$ 拆分成 $n / 2$ 个数对，根据猜想，我们得到的数对序列为：
$$
(nums[0], nums[n - 1]), (nums[1], nums[n - 2]), ... , (nums[(n / 2) - 1], nums[n / 2])
$$

换句话说，构成答案的数对必然是较小数取自有序序列的左边，较大数取自有序序列的右边，且与数组中心对称。

假设最大数对是 $(nums[i], nums[j])$，其中 $i < j$，记两者之和为 $ans = nums[i] + nums[j]$。

反证法证明，不存在别的数对组合会比 $(nums[i], nums[j])$ 更优：

假设存在数对 $(nums[p], nums[q])$ 与 $(nums[i], nums[j])$ 进行调整使答案更优。

接下来分情况讨论：

• 调整为 $(nums[i], nums[p])$ 和 $(nums[q], nums[j])$：此时最大数对答案为 $nums[q] + nums[j]$，显然 $nums[q] + nums[j] >= nums[i] + nums[j] = ans$。我们要最小化最大数对和，因此该调整方案不会让答案更好；
• 调整为 $(nums[i], nums[q])$ 和 $(nums[p], nums[j])$：此时最大数对答案为 $\max(nums[i] + nums[q], nums[p] + nums[j]) = nums[p] + nums[j] >= nums[i] + nums[j] = ans$。我们要最小化最大数对和，因此该调整方案不会让答案更好；

上述分析可以归纳推理到每一个“非对称”的数对配对中。

至此我们得证，将原本对称的数对调整为不对称的数对，不会使得答案更优，即贪心解可取得最优解。

贪心

对原数组 $nums$ 进行排序，然后从一头一尾开始往中间组「数对」，取所有数对中的最大值即是答案。

代码：

###Java

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

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

答疑

关于「证明」部分，不少小伙伴有一些疑问，觉得挺有代表性的，特意加到题解内。

Q1. 「证明」部分是不是缺少了“非对称”得最优的情况？

A1. 并没有，证明的基本思路如下：

1. 猜想对称组数对的方式，会得到最优解；

2. 证明非对称数组不会被对称数对方式更优。

然后我们证明了“非对称方式”不会比“对称方式”更优，因此“对称方式”可以取得最优解。

至于非对称和非对称之间怎么调整，会更优还是更差，我不关心，也不需要证明，因为已经证明了非对称不会比对称更优。

Q2. 证明部分的图 $p$、$q$ 是在 $i$、$j$ 内部，那么其他 $p$、$q$、$i$、$j$ 大小关系的情况呢？

A2. 有这个疑问，说明没有重点理解「证明」中的加粗部分（原话）：

上述分析可以归纳推理到每一个“非对称”的数对配对中。

也就是说，上述的分析是可以推广到每一步都成立的，包括第一步，当 $i$ 为排序数组的第一位原始，$j$ 为排序数组中最后一位时，任意 $p$ 和 $q$ 都是在 $i$、$j$ 内部的。

因此，「证明」对边界情况成立，同时对任意不成“对称”关系的数对也成立（其实也就是「证明」部分中的原话）。

更大白话一点是：对于任意“非对称”的数对组合，将其调整为“对称”数对组合，结果不会变差。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~