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

摘要： 908. Smallest Range I 題目連結 908. Smallest Range I 題目分析 給定一個數組A 和一個數字K ，找到一個在-K 和K 之間的數字x 並加到陣列A 中的每一個元素生成陣列...

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);
}
}

若覺得本文章對你有用，歡迎用愛發電 資助。