LC 910. Smallest Range II

https://leetcode.com/problems/smallest-range-ii/

我觉得这个 解答 很好. 一个突破点是对于-K/+K来说，我们可以对所有的元素统一减去K，那么这些选择就是是否+2K.

虽然这个解答很好，但总觉得这个方法不是特别显而易见的。这是一个贪心算法，但是需要证明。

Intuition:
For each integer A[i],
we may choose either x = -K or x = K.

If we add K to all B[i], the result won't change.

It's the same as:
For each integer A[i], we may choose either x = 0 or x = 2 * K.

Explanation:
We sort the A first, and we choose to add x = 0 to all A[i].
Now we have res = A[n - 1] - A[0].
Starting from the smallest of A, we add 2 * K to A[i],
hoping this process will reduce the difference.

Update the new mx = max(mx, A[i] + 2 * K)
Update the new mn = min(A[i + 1], A[0] + 2 * K)
Update the res = min(res, mx - mn)

==================

试着用Java来实现这个功能

import java.util.*;

class Solution {
    public int smallestRangeII(int[] A, int K) {
        Arrays.sort(A);
        int ans = A[A.length - 1] - A[0];
        for (int i = 0; i < A.length - 1; i++) {
            int minx = Math.min(A[0] + 2 * K, A[i + 1]);
            int maxx = Math.max(A[i] + 2 * K, A[A.length - 1]);
            ans = Math.min(ans, maxx - minx);
        }
        return ans;
    }
}