leetcode 910

问题

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] **(only once)**.

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

1
2
3
Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

1
2
3
Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

1
2
3
Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]

Note:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 10000
  3. 0 <= K <= 10000

分析

首先分析可以发现最终的结果与数组B的顺序是没有关系的，因此我们可以先将数组A从小到大进行排序。如果我们将A中所有的元素都增加K或者都减少K那么最终的答案就是A[n-1] - A[0].

对于两个元素 A[i] 和 A[j] (i < j) 时，则有A[j] > A[i]。这个时候我们再来考虑这两个元素对于加K还是减K的选择问题。当两个都选择增加K或者减少K时，这么这两个之间的差就是A[j] - A[i]，如果A[i]选择了减少K而A[j]选择了增加K，那么这两个元素之差就是 2*K + A[j] - A[i]。如果A[i] 选择了增加K而A[j] 选择了减少K时，那么这两个元素之差就是 abs(A[j]-K-A[i]-K) = abs(A[j]-A[i] - 2*k)。因此，可以看出对于 A[i] 和 A[j] 而言A[i] 选择减少K，A[j] 选择增加K一定不是最优的选择。因此，做推广可得，数组A的前一部分采取增加K，后一部分采取减少K。假设这个分界线在K，则有A[0…k] 增加K，A[k+1, … , n-1] 减少K。

这个时候最大值就是 max(A[k], A[n-1]) 最小值就是 min(A[0], A[k+1])。$s \in [0, n-1)$。先令整个数组都增加或者都减少的选择作为初始条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        int n = A.size();
        sort(A.begin(), A.end());
        int ans = A.back() - A.front();
        for (int k = 0; k+1 < n; ++k) {
            int maxNumber = max(A[k]+K, A[n-1]-K);
            int minNumber = min(A[0]+K, A[k+1]-K);
            ans = min(ans, maxNumber - minNumber);
        }
        return ans;
    }
};