題目
給你一個整數陣列 A,對於每個整數 A[i],可以選擇 x = -K 或是 x = K (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 輸出:3
解釋:B = [4,6,3]
提示:1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
解題思路分析1、遍歷;時間複雜度O(nlog(n)),空間複雜度O(1)
func smallestRangeII(A []int, K int) int { sort.Ints(A) n := len(A) res := A[n-1] - A[0] // 排序後,為了最小差值,必定是A[0,i]+K,A[i+1:]-K // 最小值落在A[0]+K,A[i+1]-K之中 // 最大值落在A[n-1]-K,A[i]+K之中 for i := 0; i < n-1; i++ { minValue := min(A[0]+K, A[i+1]-K) maxValue := max(A[n-1]-K, A[i]+K) res = min(maxValue-minValue, res) } return res}func min(a, b int) int { if a > b { return b } return a}func max(a, b int) int { if a > b { return a } return b}
總結
Medium題目,排序後,為了最小差值,在一個位置i,對於前一段有A[0,i]+K, 後一段有A[i+1:]-K;
其中最小值落在A[0]+K,A[i+1]-K之中;
其中最大值落在A[n-1]-K,A[i]+K之中;