Leetcode PHP题解--D18 908. Smallest Range I

908. Smallest Range I

题目链接

908. Smallest Range I

题目分析

给定一个数组A和一个数字K，找到一个在-K和K之间的数字x并加到数组A中的每一个元素生成数组B，返回数组B中最大值和最小值之差最小的值。

思路

根据题目，需要我们可以给数组A中的每一个元素添加-K<=x<=K中的任何一个整数，使新生成的数组B的最大值和最小值之差最小。

怎么使最大值和最小值之差最小呢？
最大值和最小值越接近中间值，最大值和最小值之差最小。

举个例子：A = [-3, 1, 3, 5, 4, 6], K = 3

先求中间值：$mid = ceil((max($A)+min($A))/2)。(-3+6)/2再向上取整为2。

再遍历每个元素。

第0个：-3要向上方求到的2靠拢，需要加2-(-3)=5。然而5>(K=3)。那么只能加K的最大值3了。-3+3=0；

第1个：1要向2靠拢，需要1，-K<=1<=K，1+1=2；

第2个：3，-K<=-1<=K，3-1=2；

第3个：5，-K<=-3<=K，5-3=2；

第4个：4，-K<=-2<=K，4-2=2；

第5个：6，-4<(-K=3)，取最小值-3，6-3=3。

我们于是得到数组B = [0,2,2,2,2,3]。最大值和最小值之差为3-0=3。

最终代码

<?php
class Solution {
    function smallestRangeI($A, $K) {
        $mid = max($K,ceil((max($A)+min($A))/2));
        $b = [];
        foreach($A as $a){
            if($a-$mid>$K && $a>=$mid){
                $b[] = $a-$K;
            }
            else if($a-$mid<$K&&$a>=$mid){
                $b[] = $mid;
            }
            else if($mid-$a<$K && $a<$mid){
                $b[] =$mid;
            }
            else if($mid-$a>$K && $a<$mid){
                $b[] = $a+$K;
            }
        }
        return max($b)-min($b);
    }
}

若觉得本文章对你有用，欢迎用爱发电资助。