题目描述
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
说明
数组长度 n 满足以下条件:
- 1 <= n <= 1000
- 1 <= m <= min(50, n)
样例
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8],
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
算法1
(二分) O(nlog(∑nums[i]))
这个题目非常关键的字眼是:非负整数数组、子数组各自(和)运算需要满足最大值最小 和 连续。尤其是「非负整数数组」和「连续」这两个信息,基本都是二分查找最典型的应用。
如果要用二分,大家需要马上想到需要证明单调性(二段性)。
使用二分查找的一个前提是「数组具有单调性」,这题想想有没有单调性,不难发现:
- 如果设置「数组各自和的最大值」很大,那么必然导致分割数很小;
- 如果设置「数组各自和的最大值」很小,那么必然导致分割数很大。
那么,我们就可以通过调整「数组各自和的最大值」来达到:使得分割数恰好为 m 的效果。这里要注意一个问题:
如果某个 数组各自和的最大值 恰恰好使得分割数为 m ,此时不能放弃搜索,因为我们要使得这个最大值 最小化,此时还应该继续尝试缩小这个 数组各自和的最大值 ,使得分割数超过 m ,超过 m 的最后一个使得分割数为 m 的 数组各自和的最大值 就是我们要找的 最小值。
题目中给出的示例)输入数组为 [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://leetcode-cn.com/problems/split-array-largest-sum/solution/er-fen-cha-zhao-by-liweiwei1419-4/
Java 代码
class Solution {
// 给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。那么二分每个连续子数组的每个总和小于等于mid
public int splitArray(int[] nums, int m) {
// start,end,mid都是连续子数组和的含义
int start = 0, end = 0x3f3f3f, mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (check(nums, m , mid)) {
end = mid;
} else {
// mid太小了,m太大了
start = mid;
}
}
if (check(nums, m , start)) {
return start;
} else {
return end;
}
}
private boolean check(int[] nums, int m, int mid) {
int sum = 0, cnt = 0;
for (int x : nums) {
if (x > mid) {
// 直接不行
return false;
}
if (sum + x > mid) {
// 新的一个子数组
sum = 0;
cnt++;
sum = x;
} else {
sum += x;
}
}
if (sum > 0) {
cnt++;
}
return cnt <= m;
}
}