【leetcode刷题】T217-最小差值 I

数学类型第33篇解题报告

leetcode第908题：最小差值 I

https://leetcode-cn.com/problems/smallest-range-i/

【题目】

给定一个整数数组 A，对于每个整数 A[i]，我们可以选择任意 x 满足 -K <= x <= 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
输出：0
解释：B = [3,3,3] 或 B = [4,4,4]

提示：

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

【思路】

这道题要是没想明白，还是有一些难度的，会想着用动态规划。

但是，我们想想，x是-K到K任意的，也就是说，所有元素都可以变大、不变或者变小。

那么，我们将大的元素变小，小的元素变大，使得数组变得平均，在取得数组最大值和最小值，他们的差不就是想要的结果吗？

再细想，我们求得原数组最大值和最小值的差res，如果这个值大于2*K，则最小结果是res-2*K；如果等于2*K，最小结果是0。

【代码】

python版本

class Solution(object):
    def smallestRangeI(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        return max(0, max(A) - min(A) - 2 * K)