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

908. Smallest Range I

题目链接

908. Smallest Range I

题目分析

给定一个数组A和一个数字K,找到一个在-KK之间的数字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<=K1+1=2

第2个:3-K<=-1<=K3-1=2

第3个:5-K<=-3<=K5-3=2

第4个:4-K<=-2<=K4-2=2

第5个:6-4<(-K=3),取最小值-36-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);
    }
}

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

skys215 has written 118 articles

没有bug的代码是有bug的代码。

积分:5827 等级:P8 职业:PHP工程师 城市:深圳

0 条回复

登录后才能进行评论,立即登录?