LeetCode 908. Smallest Range I

问题

问题描述：给定一个整形数组 A，对于 A 中的每个元素 A[i]，都可以加上一个数 x， 其中 -K <= x <= K，然后可以得到一个新数组 B。求出 B 中最大数与最小数的最小差值。

问题要点：首先需要明确的是，这里的差值是指绝对值，是 >= 0 的。让 B 中最大数与最小数的差值最小，取决于怎么加 x。

想看英文的戳这里：原题地址

解决方案

简化问题

先简化问题，假设有 a，b 两个数，且 a > b。a，b 分别加上一个数之后，a1 = a + x，b1 = b + x ，其中 -K <= x <= K，那么a1，b1 的最小差值是多少？

假设 a，b 的差值为 c = a - b。

当 a，b 各加上一个数后，其差值为 a + x1 - (b + x2) = a - b - (x2 - x1)。由于 a-b 是正数，则需要让x2 - x1 越接近 c，其差值越小，且 x2 为正数。

由于 -K <= x <= K，比较容易推断出，x2 - x1 的范围是 [-2k, 2k]，所以其最大值为 2k。

比如 c = 3，k = 2，x2 - x1 的范围在 [-4, 4]之间，也就是说完全能取到 3，所以其最小差值为 0。
比如 c = 5，k = 1，x2 - x1的最大值也只能是 2，所以最小差值为 5 - 2 = 3。

所以，按照上面的推断，我们可以比较 c 与 2k，如果c <= 2k，则最小差值为 0；如果 c > 2k，则为 c - 2k。

回到正题

那么对于A数组来说，我们只要找到其最大值 maxA、最小值 minA，转化为上面的问题即可。

那为什么能保证 maxA + x1，minA + x2 在 B 中仍然是最大值和最小值呢？因为可以操作其他元素+x，使其值一定在 minA + x1 <= B[i] <= maxA + x2之间。

比如 A = [2, 4, 9]， k = 3，那么 maxA - minA = 9 - 2 = 7，则最小差值为 7 - 2k = 1。

A -> B 变换如下，为了使得 B[1] 处于最大最小值之间，需要 +1。这只是其中的一种变换方式。

A:[2, 4, 9] => B:[2+3, 4+1, 9-3] => [5, 5, 6]

swift 代码如下：

class Solution {
    func smallestRangeI(_ A: [Int], _ K: Int) -> Int {
        if A.count <= 1 {
            return 0
        }
        
        var minA = A[0]
        var maxA = A[0]
        for a in A {
            if a > maxA {
                maxA = a
            } else if a < minA {
                minA = a
            }
        }
        
        // 最大数与最小数之差
        let difference = maxA - minA
        
        // 两个数分别加 x 后，差值范围 [-2k, 2k]，如果能补齐，则为 0
        if difference <= 2 * K {
            return 0
        } else {
            // 补最大值
            return difference - 2 * K
        }
    }
        
}