# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/sorting/smallest-range-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.