Medium

题目描述

给你一个整数数组 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
解释：将 nums 更改为 [2, 8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。

示例 3：

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

提示：

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4

解题思路

这是一道贪心算法题目。关键观察是：我们需要找到一个分界点，使得分界点左边的数都减去 k，右边的数都加上 k，这样能够最小化最大值和最小值的差。

核心思路：

  1. 排序：首先将数组排序，这样我们可以更好地分析变化后的范围。

  2. 分界点枚举：对于排序后的数组，我们枚举每个可能的分界点 i。假设 nums[0] 到 nums[i] 都加上 k，nums[i+1] 到 nums[n-1] 都减去 k。

  3. 边界计算：对于每个分界点，新的最小值可能是 nums[0] + k 或 nums[i+1] - k，新的最大值可能是 nums[i] + k 或 nums[n-1] - k。

  4. 特殊情况：还需要考虑所有数都加 k 或都减 k 的情况。

推荐解法： 排序 + 枚举分界点的贪心算法，时间复杂度 O(n log n)。

通过这种方法，我们可以在 O(n) 时间内找到每个分界点对应的最优解，从而得到全局最优解。

代码实现

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

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

public class Solution {
    public int SmallestRangeII(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length;
        int result = nums[n-1] - nums[0];
        
        for (int i = 0; i < n - 1; i++) {
            int high = Math.Max(nums[i] + k, nums[n-1] - k);
            int low = Math.Min(nums[0] + k, nums[i+1] - k);
            result = Math.Min(result, high - low);
        }
        
        return result;
    }
}

var smallestRangeII = function(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let result = nums[n-1] - nums[0];
    
    for (let i = 0; i < n - 1; i++) {
        const high = Math.max(nums[i] + k, nums[n-1] - k);
        const low = Math.min(nums[0] + k, nums[i+1] - k);
        result = Math.min(result, high - low);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
排序 + 贪心O(n log n)O(1)

说明：

  • 时间复杂度：O(n log n)，主要是排序的时间复杂度，枚举分界点的时间复杂度为 O(n)
  • 空间复杂度：O(1)，只使用了常数额外空间（不计算排序的空间消耗）