排序、贪心、滑动窗口，求数组指定加减 k 值或 k 范围内的最小差值问题。求解《908. 最小差值 I》《910. 最小差值 II》和《1984. 学生分数的最小差值》
![以数组[1， 3， 5， 6] k 等于 3 为例，增减 k 求解《最小差值》过程模拟示意图](http://s1.mtf6.com/202204301015116081_c_w_1280_ext_png.webp)
最小差值
- 已知数组，求增减
<=k最小差值- 最小值 + k → 最大值 - k
- 最小差值 = 最大值 - k - (最小值 + k) = 最大值 - 最小值 - 2 * k
- 已知数组，求增减
=k最小差值- 排序
- 贪心策略：大 - k，小 + k，越接近越好
- 存在
i，[0, i]都+ k，[i + 1, n - 1]都- k - 最小值：在
0对应值+ k和i + 1对应值- k产生 - 最大值：在
i对应值+ k和n - 1对应值- k产生 - 枚举
i，范围[0, n - 2]，不断更新最小值
- 已知数组，求范围
=k内的最小差值- 排序
- 滑动窗口：范围
[i, i + k - 1]遍历[0, n - k + 1] - 最小差值：不断更新滑动窗口的最右（大） - 最左（小）的最小值
例题
908. 最小差值 I
给你一个整数数组 nums，和一个整数 k 。 在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i ，最多 只能 应用 一次 此操作。 nums 的 分数 是 nums 中最大和最小元素的差值。 在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。
答案
顺序遍历
var smallestRangeI = function(nums, k) {
return Math.max(0, Math.max.apply(null, nums) - Math.min.apply(null, nums) - k * 2)
};var smallestRangeI = function(nums, k) {
const n = nums.length
let min = max = nums[0]
for (let i = 0; i < n; i++) {
if (nums[i] > max) max = nums[i]
if (nums[i] < min) min = nums[i]
}
return Math.max(0, max - min - k * 2)
};func smallestRangeI(nums []int, k int) int {
min, max := nums[0], nums[0]
for _, v := range nums {
if min > v {
min = v
}
if max < v {
max = v
}
}
diff := max - min - k * 2
if diff > 0 {
return diff
}
return 0
}class Solution {
function smallestRangeI($nums, $k) {
$max = $nums[0];
$min = $nums[0];
foreach ($nums as $v) {
if ($max < $v) $max = $v;
if ($min > $v) $min = $v;
}
return max(0, $max - $min - $k * 2);
}
} 910. 最小差值 II
给你一个整数数组 nums，和一个整数 k 。 对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。 nums 的 分数 是 nums 中最大元素和最小元素的差值。 在更改每个下标对应的值之后，返回 nums 的最小 分数 。
答案
贪心算法
var smallestRangeII = function(nums, k) {
nums.sort((a, b) => a - b)
const n = nums.length
let r = nums[n - 1] - nums[0]
for (let i = 0; i < n - 1; i++) {
r = Math.min(r, Math.max(nums[i] + k, nums[n - 1] - k) - Math.min(nums[0] + k, nums[i + 1] - k))
}
return r
};func smallestRangeII(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
r := nums[n - 1] - nums[0]
for i := 0; i < n - 1; i++ {
r = min(r, max(nums[i] + k, nums[n - 1] - k) - min(nums[0] + k, nums[i + 1] - k))
}
return r
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}class Solution {
function smallestRangeII($nums, $k) {
sort($nums);
$n = count($nums);
$r = $nums[$n - 1] - $nums[0];
for ($i = 0; $i < $n - 1; $i++) {
$r = min($r, max($nums[$i] + $k, $nums[$n - 1] - $k) - min($nums[0] + $k, $nums[$i + 1] - $k));
}
return $r;
}
}1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。 从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。 返回可能的 最小差值 。
答案
var minimumDifference = function(nums, k) {
nums.sort((a, b) => a - b)
const n = nums.length
let ans = 1e5
for (let i = 0; i < n - k + 1; i++) ans = Math.min(ans, nums[i + k - 1] - nums[i])
return ans
};func minimumDifference(nums []int, k int) int {
sort.Ints(nums)
r, n := int(1e5), len(nums)
for i := 0; i < n - k + 1; i++ {
r = min(r, nums[i + k - 1] - nums[i])
}
return r
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}class Solution {
function minimumDifference($nums, $k) {
sort($nums);
$n = count($nums);
$r = 10 ** 5;
for ($i = 0; $i < $n - $k + 1; $i++) $r = min($r, $nums[$i + $k - 1] - $nums[$i]);
return $r;
}
}
