908. 最小差值 I

Easy

题目描述

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

在一次操作中，你可以选择任意索引 i（其中 0 <= i < nums.length），并将 nums[i] 更改为 nums[i] + x，其中 x 是范围 [-k, k] 内的整数。你可以对每个索引 i 最多应用一次此操作。

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
输出：0
解释：将 nums 更改为 [4, 4, 4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。

提示：

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

解题思路

这道题的关键在于理解操作的本质：我们可以将数组中的每个元素在 [-k, k] 范围内调整。

核心思路： 要使最终数组的最大值和最小值差值最小，最优策略是让所有元素尽可能靠近某个中心值。

分析过程：

1. 首先找到原数组的最大值 max_val 和最小值 min_val
2. 经过调整后，最小值最多可以增加到 min_val + k，最大值最少可以减少到 max_val - k
3. 如果调整后的范围有重叠（即 min_val + k >= max_val - k），那么所有数都可以调整到同一个值，最小差值为 0
4. 如果没有重叠，最小差值就是 (max_val - k) - (min_val + k) = max_val - min_val - 2k

数学表达：

• 当 max_val - min_val <= 2k 时，结果为 0
• 否则结果为 max_val - min_val - 2k

这可以简化为：max(0, max_val - min_val - 2k)

代码实现

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int min_val = *min_element(nums.begin(), nums.end());
        int max_val = *max_element(nums.begin(), nums.end());
        return max(0, max_val - min_val - 2 * k);
    }
};

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        min_val = min(nums)
        max_val = max(nums)
        return max(0, max_val - min_val - 2 * k)

public class Solution {
    public int SmallestRangeI(int[] nums, int k) {
        int min_val = nums.Min();
        int max_val = nums.Max();
        return Math.Max(0, max_val - min_val - 2 * k);
    }
}

var smallestRangeI = function(nums, k) {
    const min_val = Math.min(...nums);
    const max_val = Math.max(...nums);
    return Math.max(0, max_val - min_val - 2 * k);
};

复杂度分析

说明：

• 时间复杂度：需要遍历数组找到最大值和最小值
• 空间复杂度：只使用了常数级别的额外空间