题目描述

给定一个整数数组 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]

算法

$O(nlogn)$

首先对这个数组进行排序，那么知道一定不存在 - + 的操作。
那么存在的序列只能是 + -。 所以枚举分界位置就好。

C++ 代码

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {        
        sort(A.begin(), A.end());
        int ans = A.back() - A[0];
        int n = A.size();
        for (int i = 0; i < n - 1; ++i) {
            int mins = min(A[0] + K, A[i + 1] - K);
            int maxs = max(A[i] + K, A.back() - K);
            ans = min(ans, maxs - mins);
        }
        return ans;
    }
};