目录

一、leetcode 908.最小差值I

二、leetcode 910.最小差值II 

---

一、leetcode 908.最小差值I

1.问题描述

给你一个整数数组 nums，和一个整数 k 。

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。

nums 的 分数 是 nums 中最大和最小元素的差值。 

在对  nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。

示例 3：

输入：nums = [1,3,6], k = 3
输出：0
解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104

2.思路

（1）要使加减操作后最大值与最小值的差值最小，只需考虑加减操作前nums中的最小值nmin与最大值nmax

（2）加减操作前nums中大于nmin小于nmax的数可以通过加减某个绝对值小于等于k的一个数，达到大于等于nmin+k1小于等于nmax-k2，所以加减操作后最小值是nmin+k1，最大值是nmax-k2

（3）nmin+k1与nmax-k2越接近越好，最好nmin+k1=nmax-k2

（4）如果nmax-nmin<=2*k,那么存在绝对值不大于k的k1,k2，使得nmin+k1=nmax-k2

3.代码 

int smallestRangeI(vector<int>& nums, int k) {
        int size=nums.size();
        int nmin=nums[0],nmax=nums[size-1];
        for(int i=0;i<size;i++)
        {
            nmin=min(nmin,nums[i]);
            nmax=max(nmax,nums[i]);
        }
    /*也可以用sort(nums.begin(),nums.end())得到最大值与最小值，
    但是没有必要对全部元素排序，这样增大时间复杂度*/
        if(nmax-nmin<=2*k) return 0;
        else return nmax-nmin-2*k;
    }

二、leetcode 910.最小差值II 

1.问题描述

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 104
• 0 <= k <= 104

 2.思路

（1）枚举分界点，分界点左边的数都+k，分界点右边的数都-k，

（2）找到此时最大值max(nums[n - 1] - k, nums[i - 1] + k)，最小值min(nums[0] + k, nums[i] - k)

（3）维护最小的极差ans

3.代码

int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int ans = nums[n - 1] - nums[0];
        for(int i=1;i<n;i++)
        {
            ans = min(ans, max(nums[n - 1] - k, nums[i - 1] + k) - min(nums[0] + k, nums[i] - k));
        }
        return ans;
    }