难度：★★★☆☆
类型：数组
方法：排序

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给你一个整数数组 A，对于每个整数 A[i]，可以选择 x = -K 或是 x = K （K 总是非负整数），并将 x 加到 A[i] 中。

在此过程之后，得到数组 B。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解答

这道题的意思是，给出一个数组，让我们对其中的所有元素进行+K或-K操作，这些操作都是我们自己选择的，目的是让操作完成后整个数组的最大值与最小值之间的差距最小。

我们把数组从小到大排序，为了削弱最大值与最小值之间的差距，理所应当的，我们需要把较大的那几个数字-K，剩下的较小的数字统统+K，问题就在于，如何去划分这两批数字。

一次前向遍历就可以实现。假设最左端和最右端的数字分别是min_num和max_num划分点处左侧和右侧的数字分别是divide_left，divide_right，因为排序的缘故，divide_left不大于divide_right，divide_left及其左半边的数字划分成一类，对这些数字进行+K操作，divide_right及其右半边的数字划分成一类，对这些数字进行-K操作。

如果我们画一条以下标为横轴，以数值为纵轴的线，这样一来，在划分点处就会出现断崖，但是分成的两段又各自是递增的。接下来就是如何求这种情况下的最大值与最小值的差值的问题。很显然，最大值一定在两个线段的右端点divide_left+K和max_num-K中产生，我们取其中最大值即可，最小值一定在两个线段的左端点min_num+K和divide_right-K中产生，我们取其中的最小值即可。这样一来，最大值与最小值一减，就获得了当前划分方式下的最大最小值之差。

我们统计一下每种划分方式下的最大最小值之差，选取其中的最小值即为题目所求。

class Solution:
    def smallestRangeII(self, A, K):
        A.sort()
        min_num, max_num = A[0], A[-1]
        ans = max_num - min_num
        for divide_left, divide_right in zip(A[:-1], A[1:]):
            ans = min(ans, max(max_num-K, divide_left+K) - min(min_num+K, divide_right-K))
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析