题目描述
难度 - 困难
410. 分割数组的最大值
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1e6
1 <= m <= min(50, nums.length)
二分法
挖掘单调性：使用二分查找的一个前提是「数组具有单调性」，我们就去想想有没有单调性可以挖掘，不难发现：
如果设置「数组各自和的最大值」很大，那么必然导致分割数很小；
如果设置「数组各自和的最大值」很小，那么必然导致分割数很大。
仔细想想，这里「数组各自和的最大值」就决定了一种分割的方法。再联系一下我们刚刚向大家强调的题目的要求 连续 和题目中给出的输入数组的特点: 非负整数数组。
那么，我们就可以通过调整「数组各自和的最大值」来达到：使得分割数恰好为 m 的效果。这里要注意一个问题：
注意事项：如果某个 数组各自和的最大值 恰恰好使得分割数为 m ，此时不能放弃搜索，因为我们要使得这个最大值 最小化，此时还应该继续尝试缩小这个 数组各自和的最大值 ，使得分割数超过 m ，超过 m 的最后一个使得分割数为 m 的 数组各自和的最大值 就是我们要找的 最小值。文章来源：https://www.toymoban.com/news/detail-686276.html
这里想不太明白的话，可以举一个具体的例子：
例如：（题目中给出的示例）输入数组为 [7, 2, 5, 10, 8] ，m = 2 。如果设置 数组各自和的最大值 为 21，那么分割是 [7, 2, 5, | 10, 8]，此时 m = 2，此时，这个值太大，尝试一点一点缩小：
设置 数组各自和的最大值 为 20，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 19，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 18，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 17，此时分割就变成了 [7, 2, 5, | 10, | 8]，这时 m = 3。
m 变成 3 之前的值 数组各自和的最大值 18 是这个问题的最小值，所以输出 18。文章来源地址https://www.toymoban.com/news/detail-686276.html
代码演示
public int splitArray(int[] nums, int k) {
int left = 0;
int right = 0;
for(int n : nums){
right += n;
left = Math.max(left,n);
}
while(left < right){
int mid = left + (right - left) / 2;
int num = f(nums,mid);
if(num <= k){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
/**
* x 是分割的大小。
*/
public int f(int[]nums,int x){
int k = 1;
int count = 0;
for(int n : nums){
if(count + n > x){
k++;
count = 0;
}
count += n;
}
return k;
}
到了这里，关于leetcode410. 分割数组的最大值(java)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
