Day71 | 灵神 | 二分查找 最小化数组中的最大值

2439.最小化数组中的最大值

2439. 最小化数组中的最大值 - 力扣（LeetCode）

灵神说看到最小化最大值就肯定是二分查找，这点要记住

思路：

还是老套路，先看二分的是什么，这道题求的是最小化的最大值，那么二分的是最大值，而不是原数组

那么二分区间即最大值的区间是多少呢？最大值肯定就是max(nums)了，最小值那肯定就是0了，或者从1开始二分也可以，都是非负数，区间就是[0,max(nums)]，笔者用的左闭右开，那就是[0,max(nums)+1)

然后套路模板就可以写了

接下来就是找判断条件，即写出check函数了

我觉得这个是最难的

由于我们二分的是最大值，所以我们就设定一个上界，这个上界就是此次的mid，即所求的符合条件的最大值，如果数组中的数字大于mid，即nums[i]>mid，那就那多余的部分，即nums[i]-mid，减到旁边的数字上面去，减到最后，如果小于的话就不作操作，最后如果数组所有的数都小于等于mid，那我们说这个mid是符合条件的

由于题目中说，只可以右边的数减给左边的，那么上面所说的旁边的数字只能是左边的，所以我们倒着减，减到最后只要nums[0]<=mid就说明mid符合条件了，因为0之后的数字都是减过的，肯定符合条件

模拟[3,7,1,6]

二分到target==5时

nums[3]=6，6>5，nums[2]+=(6-5) nums[2]=2

nums[2]=2, 2<5，不作操作

nums[1]=7, 7>5，nums[0]+=(7-5) nums[0]=5

5<=5 满足条件返回true

笔者代码如下：

注意，如果是按照我上面的写法，你的传参一定不可以传引用，而是值传递，不然修改了原数组，后面再check就肯定会出错的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool check(vector<long long> nums,int target)
    {
        for(int i=nums.size()-1;i>=1;i--)
        {
            if(nums[i]>target)
                nums[i-1]+=(nums[i]-target);
        }
        return nums[0]<=target;
    }
    int minimizeArrayValue(vector<int>& nums) {
        int l=0,r=ranges::max(nums)+1;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            vector<long long> v(nums.begin(),nums.end());
            if(check(v,mid))
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
};

所有的 long long都是为了解决溢出问题而写的，下面看看灵神是如何解决这件事的

灵神代码：

即搞一个变量extra记录溢出的部分，大于mid的部分给存储下来，加到下一个上面，如果小于mid，那就等于0，因为他的下一个数字不需要加extra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool check(vector<int> nums,int target)
    {
        long long extra=0;
        for(int i=nums.size()-1;i>=1;i--)
        {
            long long x=nums[i]+extra;
            if(x>target)
                extra=(x-target);
            else
                extra=0;
        }
        return nums[0]+extra<=target;
    }
    int minimizeArrayValue(vector<int>& nums) {
        int l=0,r=ranges::max(nums)+1;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(check(nums,mid))
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
};