908. 最小差值 I

🟢   🔖  数组 数学  🔗 力扣 LeetCode

题目

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimumscore of nums after applying the mentioned operation at most once for each index in it.

Example 1:

Input: nums = [1], k = 0

Output: 0

Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2:

Input: nums = [0,10], k = 2

Output: 6

Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3:

Input: nums = [1,3,6], k = 3

Output: 0

Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints:

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

题目大意

给你一个整数数组 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 <= 10^4
• 0 <= nums[i] <= 10^4
• 0 <= k <= 10^4

解题思路

• 目标是尽可能缩小数组中的最大值与最小值的差。
• 如果将最大值 max 减去 k，将最小值 min 加上 k，那么数组范围可能会缩小为：
  范围 = (max - k) - (min + k) = max - min - 2k
• 如果结果为负数，则数组中的所有值经过调整后可以完全重叠在一起，此时差值为 0。

1. 计算数组的最大值和最小值： 遍历数组，分别记录 max 和 min。
2. 计算差值：
   • 按照公式 范围 = max - min - 2k 计算范围。
   • 如果范围为负数，则返回 0。
3. 返回结果。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次，计算最大值和最小值。
• 空间复杂度：O(1)，仅使用了常数额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestRangeI = function (nums, k) {
	let max = 0,
		min = Infinity;

	// 遍历数组，计算最大值和最小值
	for (let num of nums) {
		max = Math.max(max, num);
		min = Math.min(min, num);
	}

	// 计算缩小后的范围
	return Math.max(max - min - 2 * k, 0);
};