410.分割数组的最大值 （二分法）------ 力扣每日打卡Day6

目录

• • 1.题目
  • 2.题目分析
  • 3.代码二分法实现
  • 4.总结

1.题目

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:

数组长度 n 满足以下条件:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

来源：力扣（LeetCode）戳我前往题目

示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

           

C语言函数头：

2.题目分析

一般这种求最小值的，会最先想到动态规划啥的，但是我技术实在是不精，没有看懂这动态规划。这种一看就有很多种分隔方法的题，我们可以换一种思维来做。既然去分组类一个个计算太复杂，就直接找那个最大值。

直接通过二分法找到合适的最大值，然后再带进数组里面分隔。

• 分割出来的组数如果小于等于m，那就说明我们找的最大值（mid）偏大，让right向左收。

• 分割出来的组数如果大于m，那就说明我们找的最大值（mid）偏小，让left 向右移。

  直到找到最后的mid，就是我们要找的最大值。

3.代码二分法实现

int count (int* nums, int numsSize, int max){
    int cou = 1;//子数组的个数
    int sum = 0;
    for(int i = 0; i < numsSize; i++){

        //单个数都比最大值大，说明最大数取值太小了，left右移
        if(nums[i] > max){ 
            return INT_MAX;
        }
        
        //比最大值小，就继续加
        if(nums[i] + sum <= max){
            sum += nums[i];
        }
        
        //如果sum比最大值大，就划分，进入下一个子数组
        else{ 
            sum = nums[i];
            cou++;
        }
    }
    return cou;
}
int splitArray(int* nums, int numsSize, int m){
    int cou;
    int left = 0,right = INT_MAX;//直接把右设置的int型的最大值
    int mid = (right - left)/2 + left; //也就是我们找的子数组和的最小的最大值
    while(left < right){
        cou = count(nums,numsSize,mid);
        if(cou <= m){ //生成的子数组个数小于等于m,说明我们找的mid太大了，应该向左移
            right = mid;
        }
        else{ //生成的子数组个数大于m,说明我们找的mid太小了，应该右移
            left = mid + 1;
        }
        mid = (right - left)/2 + left;
    }
    return mid;
}
           

4.总结

很多时候这种分割类型、分组的题，因为会有很多种情况，我就看到就想退缩了。记得多换思维，可以直接从结果出发，看起来困难的题，有时候也是很容易的。

不要畏惧他，面对他，侧面进攻！加油加油鸭！