910. Smallest Range II

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& 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation