> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/sorting/smallest-range-ii.md).

# 910. Smallest Range II

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`.

1.

**Example 1:**

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

**Example 2:**

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

**Example 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`

## Thoughts

对给定数组每个元素可选+K或-K，问选择后argmin(最大值-最小值）。最大和最小=>sorting：从小到大排序，右边那头往下压，左边的往上提，从而使得最大和最小之间的差最小。假设A\[i]是左边往上提的最右边的元素，最大值可能是A\[i] + K或A\[-1] - K，那最小值可能是A\[i + 1] - K或A\[0] + K。遍历所有的i看全局最优。

## Code

```python
class Solution:
    def smallestRangeII(self, A: List[int], K: int) -> int:
        A.sort()
        res = A[-1] - A[0]
        for i in range(len(A) - 1):
            diff = max(A[i] + K, A[-1] - K) - min(A[0] + K, A[i + 1] - K)
            res = min(res, diff)
        return res
        
```

```cpp
class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int n = A.size(), mi = A[0] + K, mx = A[n - 1] - K, res = A[n - 1] - A[0];
        for (int i = 0; i < n - 1; ++i) {
            mi = min(A[0] + K, A[i + 1] - K);
            mx = max(A[n - 1] - K, A[i] + K);
            res = min(res, mx - mi);
        }

        return res;
    }
};
```

## Analysis

时间复杂度O(nlgn)