Skip to main content

908.最小差值I

caution

原题链接：https://leetcode-cn.com/problems/smallest-range-i/

思路​

虽然题目看起来好像抽象且随机，但是其实有规律可寻。因为要找修改之后数组的最大值和最小值的差值最小。所以，应该要使得数组原本的最大值和最小值尽可能的接近，这样得到的结果才是最小的，可以发现，其实只需要操作数组的原本的最大值和最小值即可。

对于最大值而言，加上区间 [-k, k] 的最小值，也就是 -k

对于最小值而言，加上区间 [-k, k] 的最大值，也就是 k

将上述修改后的两数进行相减，就是最小值，如果相减小于 0 了，说明最大值却比最小值小，说明可调整的范围 0 就是最小值。

代码​

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int maxv = 0, minv = 0x3f3f3f3f;
        for (int i =0 ; i < nums.size(); i++) {
            maxv = max(maxv, nums[i]);
            minv = min(minv, nums[i]);
        }
        int res = (maxv - k) - (minv + k);
        return max(0, res);
    }
};