1. 題目

給定一個(gè)整數(shù)數(shù)組 A，對(duì)于每個(gè)整數(shù) A[i]，我們可以選擇 x = -K 或是 x = K，并將 x 加到 A[i] 中。

在此過程之后，我們得到一些數(shù)組 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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/smallest-range-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：LeetCode 908. 最小差值 I

• 首先 都向一側(cè)偏移，差值就是max-min
• 部分偏移的話，排序以后，左側(cè)小的+K，右側(cè)大的-K，才可能得到更小的差值
• 遍歷所有的分割點(diǎn)
  

class Solution { // c++ public:int smallestRangeII(vector<int>& A, int K) {sort(A.begin(), A.end());int i, n = A.size(), up, down;int mindis = INT_MAX;for(i = 0; i < n-1; i++){up = max(A[i]+K, A[n-1]-K);down = min(A[0]+K, A[i+1]-K);mindis = min(mindis, up-down);}return min(mindis, A[n-1]-A[0]);//第二種情況為同側(cè)偏置} };

68 ms 15 MB

class Solution: # py3def smallestRangeII(self, A: List[int], K: int) -> int:A.sort()mindis = float("inf")n = len(A)for i in range(n-1):up = max(A[i]+K, A[n-1]-K)down = min(A[0]+K, A[i+1]-K)mindis = min(mindis, up-down)return min(mindis, A[n-1]-A[0])# 第二種情況為同側(cè)偏置

212 ms 14.9 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 910. 最小差值 II（贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。