最小差值 II

难度: 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
解释：将数组变为 [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⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

Submission

运行时间: 56 ms

内存: 16.9 MB

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

Explain

此题解首先对数组进行排序，以便确定数组中的最小值和最大值。然后，考虑两种变化：对每个元素加上k或者减去k。在所有可能的情况中寻找最小的最大值与最小值的差值。通过遍历排序后的数组，并在每一步尝试将前面的元素加上k，后面的元素减去k，从而计算可能的最小分数。这是因为在排好序的数组中，较小的元素加k和较大的元素减k会有助于减小最大值与最小值之间的差距。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        n = len(nums) # 获取数组长度
        nums.sort() # 对数组进行排序
        ans = nums[-1] - nums[0] # 初始化答案为未调整前的最大差值
        for i in range(n - 1): # 遍历数组，尝试每个分割点
            high = max(nums[-1] - k, nums[i] + k) # 计算可能的最大值
            low = min(nums[i + 1] - k, nums[0] + k) # 计算可能的最小值
            ans = min(ans, high - low) # 更新结果为最小的差值
        return ans # 返回最终结果

Explore

在排序数组中，最小元素在最前面，最大元素在最后面。对前面的元素加k，意味着提高了数组的最小值；而对后面的元素减k，意味着降低了数组的最大值。这样操作后，数组的最大值和最小值都向中间靠拢，从而可能减少它们之间的差距，进而降低整个数组的范围。这是因为你在减少原本数组中最大和最小值之间的差异。

此逻辑依据的是尝试每个可能的分割点，将数组分为两部分。对于每个分割点`i`，数组在`i`处分为两部分，前半部分都加k，后半部分都减k。`nums[i]+k`表示前半部分可能的最大值，`nums[-1]-k`表示后半部分可能的最大值；类似地，`nums[0]+k`表示前半部分可能的最小值，`nums[i+1]-k`表示后半部分可能的最小值。使用`max`和`min`函数保证了在任何分割情况下，正确计算出调整后数组的最大值和最小值。

算法中的`尝试每个分割点`指的是对数组的每个元素位置进行考虑，把它视为一个潜在的分割点。数组在这个点被分为两部分：从开始到这个点的部分，我们对这部分的每个元素加k；而从这个点之后到数组结束的部分，我们对这部分的每个元素减k。这样做可以模拟所有可能的通过增加或减少k来调整数组元素值的场景，从而找到产生最小最大值差的分割方法。

初始答案设定为`nums[-1] - nums[0]`，即排序后数组的最大值和最小值的差，是因为这表示了在不进行任何加k或减k操作的情况下数组元素的最大可能差值。这是一个有效的起始分数，因为任何对数组元素进行加k或减k的操作都是试图减少这个差值。将其设为初始答案允许算法有一个基准值，从而在后续操作中寻找是否有更小的差值出现。