【04-30】力扣每日一题

题目描述

题目分析

由于今天的每日一题为“最小差值I”，那么在做完“最小差值I”之后顺带把“最小差值II”给做了，加深一下我们对这类题目的印象。首先我们来分析一下题目意思。

第一题的意思是说，给你一个数组nums，再给你一个整数k，那么对于数组里的每一个数，你可以加上一个值，这个值的范围在[-k,k]之间，当你完成了对这个数组中数据的变换之后，我们求这个数组中的最大值max和最小值min，然后max-min就是我们需要求的结果，需要注意的是，我们要使(max-min)最小。

这个题目看完之后，一般人的思路是这样的，在对数组进行操作之前，我们求出最大值max，和最小值min，然后最大值-k，最小值+k，那这样不就行了。但是我们需要注意一件事情，那就是题目中的max-min是修改完原数组之后的max和min，所以你最大值-k，最小值+k这样有可能会把最大值变得比最小值要小。

所以我们需要换个思路，假设数组修改之前，最大值为max，最小值为min。然后看题目的意思，我们是不是要缩小最大值和最小值之间的差距呢？如果是缩小最大值和最小值之间的差距，我们对max可以扰动的范围为[-k,k]，同样对min可以扰动的范围为[-k,k]，那么max-k和min+k，是不是在原来的基础上缩小了2k（max - k - min -k）。如果我们的max与min之间的距离小于等于2k，那么我们是不是可以调整到max - min = 0，也就是二者相等，对吧。如果我们的max与min之间的距离大于2k，那么我们最大是不是只能将距离减小2k，那么我们的结果为 max - min - 2k，那么代码就可以写出来了。

接着我们再来看第二题，第二题与第一题不同之处在于，第二题要求数组中的每个值都要被修改，而且修改的方法只有两种，要么+k，要么-k。我们再来分析一波，最后还是要求数组中最大值和最小值的差要尽量小。既然最大值和最小值的差尽量小，那么说明数组中的每个数据相差无几，那么我们是否可以这样想，首先将数组排序，按照从小到大的顺序排序。接着我们需要找到一个点，在该点及其以前，所有的数据都是+k，因为他们小啊，要想数据变得差不多，他们只有+k，然后该点之后的数据都-k。我们看如下的示意图即可弄懂：

代码实现

c++代码实现如下：

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int min = nums[0],max = nums[n-1];
        return max-min<2*k?0:max-min-2*k;
    }
};


class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        int n = nums.size();
        // 首先排序
        sort(nums.begin(),nums.end());
        // 其中的某个结果作为初始值
        int res = nums[n-1] - nums[0];
        // 枚举分割点
        for(int i = 1;i<n;i++){
            int min = std::min(nums[0]+k,nums[i] - k);
            int max = std::max(nums[n-1] - k,nums[i-1]+k);
            res = std::min(max-min,res);
        }
        return res;
    }
};