# 0910. Smallest Range II
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/smallest-range-ii/
## 思路
思路参考[这里](https://leetcode.com/problems/smallest-range-ii/discuss/173389/simple-C%2B%2B-solution-with-explanation)

先sort array
原本的array是```nums[0], nums[1], ..., nums[n-1]```
greedy的思想我们会发现我们需要找一个分界点```i```
让array变成```nums[0]+k, ..., nums[i]+k, nums[i+1]-k, ..., nums[n-1]-k```来获得最小的range (因为在左边随便挑一个值变成```nums[j]-k```或者```nums[j]```都可能使得答案变大)
对于```nums[0]+k, ..., nums[i]+k```, 最小值是```nums[0]+k```，最大值是```nums[i]+k```
对于```nums[i+1]-k, ... , nums[n-1]-k```, 最小值是```nums[i+1]-k```，最大值是```nums[n-1]-k```
所以我们在遍历的过程中比较两个最小值和两个最大值就能得到temp的答案
最后取最小值即可
## Code

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        left = nums[0]+k
        right = nums[-1]-k
        ans = nums[-1]-nums[0]

        for i in range(len(nums)-1):
            minVal = min(left, nums[i+1]-k)
            maxVal = max(right, nums[i]+k)
            ans = min(ans, maxVal-minVal)

        return ans

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[n-1]-nums[0];
        int left = nums[0]+k;
        int right = nums[n-1]-k;
        for(int i=0; i<nums.length-1; i++){
            int min = Math.min(left, nums[i+1]-k);
            int max = Math.max(right, nums[i]+k);
            ans = Math.min(max-min, ans);
        }
        return ans;
    }
}