You are given an integer array nums and an integer k.
For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.
The score of nums is the difference between the maximum and minimum elements in nums.
Return the minimum score of nums after changing the values at each index.
Example 1:
Input: nums = [1], k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
Example 2:
Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
Example 3:
Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104
最小差值 II。
给你一个整数数组 nums，和一个整数 k 。对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。
nums 的 分数 是 nums 中最大元素和最小元素的差值。
在更改每个下标对应的值之后，返回 nums 的最小 分数 。
思路
这道题是 908 题的版本二，题意跟 908 题稍有不同。在这道题里，对于每个元素 nums[i] 而言，你必须做 +k 或 -k 的操作。这道题我参考了这个帖子，写的很好，图示也很清楚。
如果没有 k，那么这道题和 908 题一样，直接求最大值和最小值差值即可。但是因为牵涉到 k 的操作了，而且我们要找的这个差值 (max - min) 需要尽可能小，所以基本的思路是要让小的数字尽可能大（那就 + k），让大的数字尽可能小（那就 - k）。但是在操作的过程中极有可能导致 min + k 比 max - k要大。所以我们不能只考虑这两个值，还要考虑中间的那些值。
所以对于任何一个中间的 index i 而言，他左侧的元素是 nums[0] 到 nums[i - 1]；他右侧的元素是 nums[i] 到 nums[n - 1]。nums[0] 到 nums[i - 1] 都要 + k，nums[i] 到 nums[n - 1] 都要 - k。
这样一来，
- 最大值就是
nums[n - 1] - k和nums[i - 1] + k的最大值 - 最小值就是
nums[i] - k和nums[0] + k的最小值
复杂度
时间O(nlogn) - sort
空间O(1)
代码
Java实现
class Solution {
public int smallestRangeII(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
int min = nums[0];
int max = nums[n - 1];
int res = max - min;
for (int i = 1; i < n; i++) {
max = Math.max(nums[i - 1] + k, nums[n - 1] - k);
min = Math.min(nums[0] + k, nums[i] - k);
res = Math.min(res, max - min);
}
return res;
}
}