最小差值 I

标签: 数组 数学

难度: Easy

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

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i ，最多 只能 应用 一次 此操作。

nums 的 分数 是 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 <= 104
  • 0 <= nums[i] <= 104
  • 0 <= k <= 104

Submission

运行时间: 24 ms

内存: 17.6 MB

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

Explain

题解的核心思路是通过调整数组中元素的值来最小化数组中最大值和最小值的差值。首先通过计算数组中的最大值和最小值，然后考虑将最小值增加最多k，将最大值减少最多k，从而尝试减少这两者之间的差。计算调整后的差值为 (max(nums) - k) - (min(nums) + k) = max(nums) - min(nums) - 2*k。然后，取上述差值与0的最大值，以确保不返回负数，因为分数不能是负的。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        # 计算数组中的最大值
        max_val = max(nums)
        # 计算数组中的最小值
        min_val = min(nums)
        # 计算调整k值后的最大分数差，并确保结果不为负数
        return max(0, max_val - min_val - 2 * k)

Explore

是的，这样的操作在大多数情况下确实能达到最小的分数差。这种方法的目的是尽可能缩小最大值和最小值之间的距离。通过将最小值增加至多k，以及将最大值减少至多k，我们实质上是在尽量使数组的范围靠拢。然而，如果两者之间的差距小于或等于2k，那么最大值和最小值可以完全重合或非常接近，从而使差值变为0或非常小。

如果`k`的值非常大，超过了`max(nums) - min(nums)`的一半，那么公式`max(nums) - min(nums) - 2 * k`会得到一个负数。这是因为减少的总量（2 * k）会超出最大值和最小值之间的原始差值。在这种情况下，按照题解中的公式，最终的差值会通过`max(0, max_val - min_val - 2 * k)`计算，确保不会返回负数，而是返回0。这意味着，即使k值非常大，公式仍然适用，因为我们通过取最大值来处理负数情况，确保最小差值不会小于0。

是的，结果可能出现负数。这种情况发生在当k的值非常大时，特别是当k大到可以使得调整后的最小值大于或等于调整后的最大值时。此时`max(nums) - min(nums) - 2 * k`的计算结果会是负数。为了确保算法返回一个合理的、非负的分数差，我们使用`max(0, ...)`来确保任何负数结果都会被修正为0。

在这个特定的问题中，使用额外的数据结构可能不会带来明显的性能提升或代码简洁性，因为本质上我们只需要计算数组中的最大值和最小值，这可以通过简单的一次遍历实现。加入额外的数据结构如堆（用于动态获取最大值和最小值）或排序数组可能会增加实现的复杂度，而不一定带来效率上的提升。当前算法的时间复杂度已经是O(n)，这是因为计算最大值和最小值各需要一次遍历，而空间复杂度是O(1)，这已经是最优解了。