0910-最小差值 II

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 **** nums[i] + k 或
nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

示例 1：

**输入：** nums = [1], k = 0
**输出：** 0
**解释：** 分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

**输入：** nums = [0,10], k = 2
**输出：** 6
**解释：** 将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

**输入：** nums = [1,3,6], k = 3
**输出：** 3
**解释：** 将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 104
  • 0 <= k <= 104

方法 1：线性扫描

想法

如 最小差值 I 问题的解决方法，较小的 A[i] 将增加，较大的 A[i] 将变小。

算法

我们可以对上述想法形式化表述：如果 A[i] < A[j]，我们不必考虑当 A[i] 增大时 A[j] 会减小。这是因为区间 (A[i] + K, A[j] - K) 是 (A[i] - K, A[j] + K) 的子集（这里，当 a > b 时 (a, b) 表示 (b, a) ）。

这意味着对于 (up, down) 的选择一定不会差于 (down, up)。我们可以证明其中一个区间是另一个的子集，通过证明 A[i] + K 和 A[j] - K 是在 A[i] - K 和 A[j] + K 之间。

对于有序的 A，设 A[i] 是最大的需要增长的 i，那么 A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K 就是计算结果的唯一值。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int smallestRangeII(int[] A, int K) {
        int N = A.length;
        Arrays.sort(A);
        int ans = A[N-1] - A[0];

        for (int i = 0; i < A.length - 1; ++i) {
            int a = A[i], b = A[i+1];
            int high = Math.max(A[N-1] - K, a + K);
            int low = Math.min(A[0] + K, b - K);
            ans = Math.min(ans, high - low);
        }
        return ans;
    }
}
[]
1
2
3
4
5
6
7
8
9
class Solution(object):
    def smallestRangeII(self, A, K):
        A.sort()
        mi, ma = A[0], A[-1]
        ans = ma - mi
        for i in xrange(len(A) - 1):
            a, b = A[i], A[i+1]
            ans = min(ans, max(ma-K, a+K) - min(mi+K, b-K))
        return ans

复杂度分析

  • 时间复杂度：O(N \log N)，其中 N 是 A 的长度。
  • 空间复杂度：O(1)，额外空间就是自带排序算法的空间。
 Comments
On this page
0910-最小差值 II