「最小差值 I」：k 是可伸缩的

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

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

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

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

假设整数数组 nums 的最小值为 minNum，最大值为 maxNum。使用数学方法不难证明以下定理：

定理：如果 maxNum-minNum≤2k，那么我们总可以将整数数组 nums 的所有元素都改为同一个整数，因此更改后的整数数组 nums 的最低分数为 0。

证明：因为 maxNum-minNum≤2k，所以存在整数 $x∈[minNum,maxNum]$ ，使得 $x-minNum≤k$ 且 $maxNum-x≤k$ 。那么整数数组 nums 的所有元素与整数 x 的绝对差值都不超过 k，即所有元素都可以改为 x。

定理：如果

maxNum-minNum>2k

，那么更改后的整数数组 nums 的最低分数为

maxNum-minNum-2k

。

证明：对于 minNum 和 maxNum 两个元素，我们将 minNum 改为 $minNum+k$ ，maxNum 改为 $maxNum-k$ ，此时两个元素的绝对差值最小。因此更改后的整数数组 nums 的最低分数大于等于 $maxNum-minNum-2k$ 。

对于整数数组 nums 中的元素 x，如果 $x<minNum+k$ ，那么 x 可以更改为 $minNum+k$ ，如果 $x>maxNum-k$ ，那么 x 可以更改为 $maxNum-k$ ，因此整数数组 nums 的所有元素都可以改为区间 $[minNum+k,maxNum-k]$ 的整数，所以更改后的整数数组 nums 的最低分数小于等于 $maxNum-minNum-2k$ 。

综上所述，更改后的整数数组 nums 的最低分数为 maxNum-minNum-2k。

public int smallestRangeI(int[] nums, int k) {
	// 找到最大最小值minNum，maxNum
	int minNum=Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
	for(int e:nums){
		minNum = Math.min(min,e);
		maxNum = Math.max(max,e);
	}
	int res = maxNum - minNum;
	return res<=2*k ? 0 : res - 2*k;
}

复杂度分析：

时间复杂度： $O(n)$ ，其中 n 是整数数组 nums 的长度。需要 $O(n)$ 的时间遍历数组 nums 得到最小值和最大值，然后需要 $O(1)$ 的时间计算最低分数。
空间复杂度： $O(1)$ 。

「最小差值 II」：k 是不可伸缩的

题目：🟨 910. 最小差值 II - 力扣（LeetCode）

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

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

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

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

首先我们考虑将数字 nums 排一下序。

假设将全部数字都 +k 或都 -k，分数是不变的。

一个最朴素的思路是，将小的数 +k，将大的数 -k，试图减少 nums 的分数。

我们的目标就是将排好序的 nums 中间「切一刀」，让左边的数 +k，右边的数都 -k，然后检查数组 nums 的分数。根据这个思路，我们可以从左到右遍历不断的「切」从而找到答案。至于为什么这种想法是对的，可以继续看下面的思考。

public int smallestRangeII(int[] nums, int k) {
	int len = nums.length;
	if(len==1)return 0;
	Arrays.sort(nums);
	int min = nums[0]+k,max = nums[len-1]-k;
	int res = nums[len-1]-nums[0];
	for(int i=0;i<len-1;i++){
		int high = Math.max(nums[i]+k,max);
		int low = Math.min(nums[i+1]-k,min);
		res = Math.min(res,high-low);
	}
	return res;
}

复杂度分析：

时间复杂度： $O(N \log N)$ ，其中 N 是 A 的长度。
空间复杂度： $O(1)$ ，额外空间就是自带排序算法的空间。

在上面的算法中，我们在寻找「切一刀」的位置时，相当于只是考察了左边的数都 +k，右边的数都 -k 的情况。那么，我们需不需要考察这样一种情况：+k 的数和 -k 的数并不分居两侧，而是穿插交替进行，比如下面的这样一个情况。

答案是不需要的。上图中，设最右边的选择 +k 的数 nums[k] 的左侧存在一个进行了 -k 操作的数——比如 nums[i]。将 nums[i] 转变为 +k 操作总是有利的——因为它不会增大当前照片中 nums 的分数 res：

假设 nums[i]-k 是当前数组最小值，转变为 +k 操作后，可能会将当前数组 nums 的最小值提高。
假设 nums[i]-k 不是当前数组最小值，转变为 +k 操作后，不会影响当前数组 nums 的最小值。
将 nums[i] 转换为 +k 操作后，nums[i]+k 不可能大于 nums[k]+k（因为 nums[i] 在 nums[k] 的左侧，所以 nums[i]<=nums[k]，所以 nums[i]+k<=nums[k]+k）。也就是说这个操作不会增大当前数组 nums 的最大值。
因此，这种转变操作总是有益的。