0910. 最小差值 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 贪心

1. 📝 题目描述

• leetcode

给你一个整数数组 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 <= 10^4
• 0 <= nums[i] <= 10^4
• 0 <= k <= 10^4

2. 🎯 s.1 - 排序 + 贪心

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int smallestRangeII(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int n = numsSize;
    int res = nums[n - 1] - nums[0];
    for (int i = 0; i < n - 1; i++) {
        int hi = nums[i] + k > nums[n - 1] - k ? nums[i] + k : nums[n - 1] - k;
        int lo = nums[0] + k < nums[i + 1] - k ? nums[0] + k : nums[i + 1] - k;
        int d = hi - lo;
        if (d < res) res = d;
    }
    return res;
}

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestRangeII = function (nums, k) {
  nums.sort((a, b) => a - b)
  const n = nums.length
  let res = nums[n - 1] - nums[0]
  for (let i = 0; i < n - 1; i++) {
    const hi = Math.max(nums[i] + k, nums[n - 1] - k)
    const lo = Math.min(nums[0] + k, nums[i + 1] - k)
    res = Math.min(res, hi - lo)
  }
  return res
}

py

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        res = nums[-1] - nums[0]
        for i in range(n - 1):
            hi = max(nums[i] + k, nums[-1] - k)
            lo = min(nums[0] + k, nums[i + 1] - k)
            res = min(res, hi - lo)
        return res

• 时间复杂度：$O(n\log n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$

算法思路：

• 排序后枚举分割点 i，左侧 +k 右侧 -k
• 最大值为 max(nums[i]+k, nums[n-1]-k)，最小值为 min(nums[0]+k, nums[i+1]-k)