题目描述

给定一个整数数组 A，对于每个整数 A[i]，我们可以选择 x = -K 或是 x = K，并将 x 加到 A[i] 中。

在此过程之后，我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

样例

输入：A = [1], K = 0
输出：0
解释：B = [1]

输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]

输入：A = [1,3,6], K = 3
输出：3
解释：B = [4,6,3]

注意

• 1 <= A.length <= 10000
• 0 <= A[i] <= 10000
• 0 <= K <= 10000

算法

(排序后枚举) $O(n \log n)$

1. 我们肯定期望在较小的数字上增加 K，在较大的数组上减少 K，所以首先将数组 A 从小到大排序。
2. 初始化答案为 A[n - 1] - A[0]；然后依次枚举每个位置 i，计算此时的最小值 min(A[0] + K, A[i + 1] - K) 和最大值 max(A[i] + K, A[n - 1] - K)，然后更新答案。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，然后一次线性遍历，时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅使用了常数的空间，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        int n = A.size();

        sort(A.begin(), A.end());

        int ans = A[n - 1] - A[0];
        for (int i = 0; i < n - 1; i++) {
            int minr = min(A[0] + K, A[i + 1] - K);
            int maxr = max(A[i] + K, A[n - 1] - K);
            ans = min(ans, maxr - minr);
        }

        return ans;
    }
};