[LeetCode] 910. Smallest Range II

[grandyang]

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6 Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]

Note:

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

这道题是之前那道 Smallest Range I 的拓展，那道题说的是每个数字可以加上 [-K, K] 范围内的任意一个数字，这道题说是每个数字必须加上K或者 —K，都是问新数组的最大值最小值之间的差值最小是多少。这两个条件有显著的区别，对于前一道题来说，非常的 flexible，因为可以加上 [-K, K] 范围内的任意一个数字，就是说也可以加上0，从而数字保持不变，那么只需要对原数组的最大值最小值进行修改即可，而这道题所有数字都强制要进行修改，则只考虑最大值最小值显然是不对的。来想想为什么不能直接对最小值加K，最大值减K，然后算差值。来看题目中的例子3，A = [1,3,6], K = 3，对最小值加K，得到4，对最大值减K，得到3，相减得到 -1，但实际上是不对的，因为中间的3也要进行加减操作，只能变成0或6，这样相当于改变了新数组的最大值最小值，最终算下来的结果应该是3。博主其实也尝试了暴力搜索法，即将原数组中的每个数字进行加K和减K，把得到的两个新数字放到一个新数组中，最后遍历新数组，找出最大值最小值并做差，结果超时了 Time Limit Exceeded！即便这只是一道 Medium 的题目，仍然不许我们用如此 Naive 的方法。只能另辟蹊径了。

如果不考虑数字修改，那么原数组的最大值最小值之间的差值就是所求，这里可以当作结果 res 的初始值。由于每个数字都需要加K或者减K，为了使得新数组的最大值最小值的差值最小，应该尽量使原数组中的较小的数字加K，较大的数字减K，所以最好是先给原数组排个序，然后在数组的某个位置i为界限，将原数组分为两段，前面所有的数字都加K，后面所有的数字都减K。则前半段 [0, i] 中的最大值是 A[i]+K，最小值是 A[0]+K，后半段 [i+1, n-1] 范围内的最大值是 A[n-1]-K，最小值是 A[i+1]-K，所以整个数组的最大值是 A[i]+K 和 A[n-1]-K 中的较大值，最小值是 A[0]+K 和 A[i+1]-K 中的较小值，二者做差就是可能的结果了，遍历所有的i，用每次计算出的差值来更新结果 res 即可，参见代码如下：

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

Github 同步地址:

#910

类似题目：

Smallest Range I

参考资料：

https://leetcode.com/problems/smallest-range-ii/

https://leetcode.com/problems/smallest-range-ii/discuss/173377/C%2B%2BJavaPython-Add-0-or-2-*-K

https://leetcode.com/problems/smallest-range-ii/discuss/173389/simple-C%2B%2B-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)