最小差值 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会有助于减小最大值与最小值之间的差距?
▷🦆
在循环中使用`max(nums[-1] - k, nums[i] + k)`和`min(nums[i + 1] - k, nums[0] + k)`来计算可能的最大值和最小值的逻辑依据是什么?
▷🦆
算法中提到的`尝试每个分割点`是指什么?具体是如何操作的?
▷🦆
在题解中,为什么初始答案被设定为`nums[-1] - nums[0]`,这是否总是一个有效的起始分数?
▷