leetcode
leetcode 801 ~ 850
最小差值 II

最小差值 II

难度:

标签:

题目描述

代码结果

运行时间: 56 ms, 内存: 16.9 MB


/*
题目思路:
对于每个元素,可以选择增加或减少k,使得数组中的最大值和最小值的差值最小。
由于可以对每个元素进行+/- k,最大值会变成 max(nums) - k,最小值会变成 min(nums) + k。
因此,最小分数为 (max(nums) - k) - (min(nums) + k) = max(nums) - min(nums) - 2 * k。
使用Java Stream API来实现。
*/
import java.util.Arrays;
public class MinimizeScoreStream {
    public int smallestRangeI(int[] nums, int k) {
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        return Math.max(0, max - min - 2 * k);
    }
}

解释

方法:

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

时间复杂度:

O(n log n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在排序数组中对前面的元素加k而后面的元素减k会有助于减小最大值与最小值之间的差距?
在排序数组中,最小元素在最前面,最大元素在最后面。对前面的元素加k,意味着提高了数组的最小值;而对后面的元素减k,意味着降低了数组的最大值。这样操作后,数组的最大值和最小值都向中间靠拢,从而可能减少它们之间的差距,进而降低整个数组的范围。这是因为你在减少原本数组中最大和最小值之间的差异。
🦆
在循环中使用`max(nums[-1] - k, nums[i] + k)`和`min(nums[i + 1] - k, nums[0] + 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]`,这是否总是一个有效的起始分数?
初始答案设定为`nums[-1] - nums[0]`,即排序后数组的最大值和最小值的差,是因为这表示了在不进行任何加k或减k操作的情况下数组元素的最大可能差值。这是一个有效的起始分数,因为任何对数组元素进行加k或减k的操作都是试图减少这个差值。将其设为初始答案允许算法有一个基准值,从而在后续操作中寻找是否有更小的差值出现。

相关问题