最小差值

1. 题目描述

给你一个整数数组 nums，和一个整数 k 。 对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。 nums 的 分数 是 nums 中最大元素和最小元素的差值。 在更改每个下标对应的值之后，返回 nums 的最小 分数 。

样例输入 #1

输入：nums = [1], k = 0

样例输出 #1

输出：0 解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

2. 分析

如果 nums[i] 小于 nums[j]，我们不必考虑当 nums[i] 增大时 nums[j] 会减小。这是因为区间 (nums[i]+k,nums[j]−k) 是 (nums[i]−k,nums[j]+k) 的子集。其中当 a>b 时, (a,b) 表示 (b,a)。 这意味着对于 (up,down) 的选择一定不会差于 (down,up)。我们可以证明其中一个区间是另一个的子集，通过证明 nums[i]+k 和 nums[j]−k 是在 nums[i]−k 和 nums[j]+k 之间。 对于有序的数组，设 nums[i] 是最大的需要增长的 i，那么 nums[0]+k,nums[i]+k, nums[i+1]−k,nums[n−1]−k 就是计算结果的唯一值。 时间复杂度：O(nlogn)，其中 n 是数组的长度。 空间复杂度：O(1)，额外空间就是自带排序算法的空间。

3. 代码

 class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int mi = nums[0], ma = nums.back();
        int res = ma - mi;
        for (int i = 0; i < nums.size() - 1; i++) {
            int a = nums[i], b = nums[i + 1];
            res = min(res, max(ma - k, a + k) - min(mi + k, b - k));
        }
        return res;
    }
};