题目描述

给定一个数组 nums，每次操作你可以选择 nums 中的任意一个数字并将它改成任意值。

请你返回三次操作后，nums 中最大值与最小值的差的最小值。

样例

输入：nums = [5,3,2,4]
输出：0
解释：将数组 [5,3,2,4] 变成 [2,2,2,2]。
最大值与最小值的差为 2-2 = 0。

输入：nums = [1,5,0,10,14]
输出：1
解释：将数组 [1,5,0,10,14] 变成 [1,1,0,1,1]。
最大值与最小值的差为 1-0 = 1。

输入：nums = [6,6,0,1,1,4,6]
输出：2

输入：nums = [1,5,6,14,15]
输出：1

限制

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

算法

(贪心) $O(n \log n)$

1. 如果数字的个数小于等于 3 个，则答案为 0。（其实 4 个数字也是 0）。
2. 将数组从小到大排序。直觉上看，我们会修改最大的若干个数字或者最小的若干个数字。
3. 有四种选择，修改最小的三个数字，修改最小的两个数字和最大的数字，修改最小的数字和最大的两个数字，以及修改最大的三个数字。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，故总时间复杂度为 $O(n \log n)$。
• 其实可以通过找最大的三个数字和最小的三个数字将时间复杂度降为线性，但实现起来相对复杂。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minDifference(vector<int>& nums) {
        if (nums.size() <= 3)
            return 0;

        sort(nums.begin(), nums.end());

        int n = nums.size();
        return min(min(nums[n - 1] - nums[3], nums[n - 2] - nums[2]),
                   min(nums[n - 3] - nums[1], nums[n - 4] - nums[0]));
    }
};