二分查找 + 贪心
解题思路
可以用于查找一个 有范围的 整数，就能想到是不是可以使用二分查找去解决这道问题；
设计一个算法使得这 k 个子数组各自和的最大值最小 这句话比较绕：
- 将数组分割成 k 个非空的连续子数组，多个子数组分别求和，获取其中的最大值；
- 分割成 k 个非空的连续子数组有很多种分割方式，只想要 最大值最小的 这一种分割方式，并输出这个最大值；
可以转化成 在 k 个子数组各自和的最大值 的集合中，找到最小值的二分搜索；
- 如果设置「数组各自和的最大值」很大，那么必然导致分割数 k’ 很小，需要将 k’ 调大，则需要将「数组各自和的最大值」调小，即 [left, mid] ；
- 如果设置「数组各自和的最大值」很小，那么必然导致分割数 k‘ 很大，需要将 k’ 调小，则需要将「数组各自和的最大值」调大，即 [mid + 1, right] ；
- 调到
k’ === k时，就找到了满足题意的最小的最大值；先找到二分的边界，是 对答案的二分 ，即在 分割成 k 个非空的连续子数组求和后最大值 的集合中寻找最大值 最小的 那一个；
- left 指针指向 数组中最大的值 ，如果
k === nums.length则子数组的最大值就是 数组中最大的值；- right 指针指向 数组总和 ，由于
k >= 1则会分割成一个子数组即是数组本身，则范围最大值是 数组总和；那如何对数组进行切割呢？贪心地模拟分割的过程，从前到后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量（包括当前子数组），那么每当 sum 加上当前值超过了
x，就把当前取的值作为新的一段分割子数组的开头，并将 cnt 加 1
- 设置「数组各自和的最大值」=== 21，那么分割后是 [7, 2, 5, | 10, 8]，k = 2，这个值太大，尝试一点一点缩小：
- 设置「数组各自和的最大值」=== 20，此时分割后是 [7, 2, 5, | 10, 8]，k = 2；
- 设置「数组各自和的最大值」=== 19，此时分割后是 [7, 2, 5, | 10, 8]，k = 2；
- 设置「数组各自和的最大值」=== 18，此时分割后是 [7, 2, 5, | 10, 8]，k = 2；
- 设置「数组各自和的最大值」=== 17，此时分割后是 [7, 2, 5, | 10, | 8]，这时 k = 3；
- k 变成 3 之前的值，「数组各自和的最大值」 为 18 是这个问题的最小值，所以输出 18；
复杂度
-
时间复杂度：
O(nlog(sum − maxn))，其中 sum 表示数组 nums 中所有元素的和，maxn 表示数组所有元素的最大值；每次二分查找时，需要对数组进行一次遍历，时间复杂度为O(n) -
空间复杂度：
O(1)
代码实现
function splitArray(nums, k) {
let left = Math.max(...nums);
let right = nums.reduce((sum, curr) => sum += curr, 0);
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (split(nums, mid) > k) {
// 需要将 k’ 调小
// 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
// 下一轮搜索的区间是 [mid + 1, right]
left = mid + 1;
} else {
// 需要将 k’ 调大
// 下一轮搜索的区间是上一轮的反面区间 [left, mid]
right = mid;
}
}
return left;
}
/***
* @param nums 原始数组
* @param maxIntervalSum 子数组各自的和的最大值
* @return 满足不超过「子数组各自的和的最大值」的分割数 k’
*/
function split(nums, maxIntervalSum) {
let cnt = 1; // k’ >=1，分割数大于等于 1
let curIntervalSum = 0; // 当前子数组的和
for (const num of nums) {
// 每当 sum 加上当前值超过了 x，就把当前取的值作为新的一段分割子数组的开头，并将 cnt 加 1
if (curIntervalSum + num > maxIntervalSum) {
curIntervalSum = 0;
cnt++;
}
curIntervalSum += num;
}
return cnt; // 切割数
}
动态规划
解题思路
复杂度
代码实现
// 先欠着
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 875. 爱吃香蕉的珂珂
上一篇
评论
