最小差值 II

> Problem: 910. 最小差值 II

题目描述

给定一个整数数组 nums 和一个整数 k，你可以对数组中的每个元素 nums[i] 执行一次变更操作：将其加上或减去 k。操作后的数组的分数定义为该数组中的最大元素与最小元素的差值。你的任务是返回经过操作后的数组的最小分数。

示例

1. 输入：nums = [1], k = 0

   • 输出：0
   • 解释：数组的最大值和最小值都是 1，因此差值为 0。

2. 输入：nums = [0, 10], k = 2

   • 输出：6
   • 解释：可以将数组变为 [2, 8]，此时最大值是 8，最小值是 2，差值为 6。

3. 输入：nums = [1, 3, 6], k = 3

   • 输出：3
   • 解释：可以将数组变为 [4, 6, 3]，此时最大值是 6，最小值是 3，差值为 3。

解题思路

这个问题的本质是如何通过对每个元素进行 +k 或 -k 操作，将数组的最大值和最小值尽量靠近，从而最小化差值。

关键观察

1. 操作后，数组的最大值可能是原最大值减去 k 或原最小值加上 k。
2. 操作后，数组的最小值可能是原最小值加上 k 或原最大值减去 k。

因此，问题可以转化为：如何通过选择对每个元素加 k 还是减 k，来最小化数组中最大值与最小值的差距？

我们可以利用以下几条规则：

• 最大值：如果我们对数组的最大值减去 k，而对最小值加上 k，能够将最大值和最小值尽量靠近。
• 最小化差值：问题转化为我们需要尽量靠近 最大值减 k 和 最小值加 k 的差距。

具体步骤

1. 排序数组。这样可以方便地找到数组中的最小值和最大值。
2. 考虑极限情况，最大值和最小值的可能调整情况分别是：最大值减去 k 和最小值加上 k。
3. 计算最大差值，比较调整后差值的最小情况。

代码实现

class Solution {
public:int smallestRangeII(vector<int>& nums, int k) {// 将数组排序sort(nums.begin(), nums.end());int n = nums.size();// 初始分数是最大值与最小值的差int result = nums[n - 1] - nums[0];// 遍历数组，尝试调整for (int i = 0; i < n - 1; i++) {int high = max(nums[n - 1] - k, nums[i] + k);  // 调整后的最大值int low = min(nums[0] + k, nums[i + 1] - k);   // 调整后的最小值result = min(result, high - low);              // 更新最小分数}return result;}
};

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，遍历数组的时间复杂度是 O(n)。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

解释

1. 排序：我们首先对数组进行排序，便于确定最大值和最小值的候选项。
2. 遍历调整：通过遍历数组，我们尝试每一对相邻元素的调整组合来最小化最大差值。
3. 更新最小分数：我们对每一个可能的调整组合计算最大值和最小值，并不断更新最小分数。

总结

这道题的关键在于理解如何利用加 k 和减 k 操作来最小化最大值和最小值之间的差距。通过排序和遍历相邻元素的组合，可以有效地找到最优解。