LeetCode 410. 分割数组的最大值
题目描述
题意分析
将非负整数数组按原顺序切成恰好
k个非空连续子数组，使这些子数组的和中的最大值尽可能小。不能重新排列元素，每个元素必须属于某一段，且题目保证1 <= k <= n。直接枚举所有切点组合代价很大。可以反过来问：若每一段的和都不能超过某个上限
limit，能否用不超过k段装下整个数组？上限越宽松越容易满足，便能在可能的答案范围上二分。
解法：二分答案 + 贪心判定
核心思路
[!blue]
答案至少是最大元素
M，因为包含它的那一段不可能有更小的和；总和S则一定是可行上限，因为把数组合为一段就不会超过它，之后还可以继续拆分。因此二分范围为[M, S]，判定时也保证每个单独元素都能放入一段。对给定上限，顺序累加当前段。加入下一个数后仍不超过
limit就继续，只有超限才在它之前切开，并以这个数开始新段。parts记录已经开启的段数，sum记录当前段的和；每一段都向右延伸到不能继续为止。这种贪心为什么得到最少段数？第一段已经是该上限下最长的合法前缀。假设贪心的前若干段覆盖位置不早于另一种切法，若它已覆盖对方下一段的终点，自然不会落后；否则，从贪心下一段起点到那个终点，只剩对方下一段的一个后缀。由于元素非负，这个后缀的和也不会超过上限，贪心至少能覆盖到那里。因此使用相同段数时，贪心覆盖的位置始终不会落后。逐段比较可知，其他方案不可能用更少的段数覆盖整个数组。
如果贪心得到的最少段数超过
k，这个上限就不可行；如果不超过k，则可以满足题目的恰好k段。原因是非负数组的一段拆成两段后，各自的和都不会变大；只要段数仍少于k <= n，就至少还有某段包含多个元素，可以继续拆成非空段。增大上限后，原本合法的切法仍然合法，所以可行性只会从假变真，不会再变回假。中点可行时，它可能就是最小可行值，令
right = mid保留；不可行时，它以及更小的上限都可以排除，令left = mid + 1。搜索范围每轮缩小，收敛位置就是最小可行上限，也就是最小的最大段和。
k = 1时最终只能取总和，k = n时可以每个元素单独一段，答案为最大元素；全部为零时初始边界相等，直接返回零。
解题步骤
- 扫描数组，设置二分下界为最大元素，上界为总和。
- 当
left < right时，计算候选上限mid。- 判定时从一段、当前和为零开始扫描；若加入当前数会超限，就增加段数，并令新段和等于当前数。
- 段数一旦超过
k就返回不可行；扫描完成仍未超出则可行。- 可行时令
right = mid，否则令left = mid + 1；最终返回相遇位置。
代码实现
class Solution {
public int splitArray(int[] nums, int k) {
int left = 0;
int right = 0;
for (int num : nums) {
left = Math.max(left, num);
right += num;
}
while (left < right) {
int mid = left + (right - left) / 2;
// 可行上限仍可能是最小答案，收缩时保留它。
if (canSplit(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canSplit(int[] nums, int k, int limit) {
int parts = 1;
int sum = 0;
for (int num : nums) {
if (sum + num > limit) {
parts++;
// 超限时当前元素开启新段，不能漏掉它。
sum = num;
if (parts > k) {
return false;
}
} else {
sum += num;
}
}
return true;
}
}
func splitArray(nums []int, k int) int {
left, right := 0, 0
for _, num := range nums {
if num > left {
left = num
}
right += num
}
for left < right {
mid := left + (right-left)/2
// 可行上限仍可能是最小答案，收缩时保留它。
if canSplit(nums, k, mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func canSplit(nums []int, k, limit int) bool {
parts, sum := 1, 0
for _, num := range nums {
if sum+num > limit {
parts++
// 超限时当前元素开启新段，不能漏掉它。
sum = num
if parts > k {
return false
}
} else {
sum += num
}
}
return true
}
复杂度分析
设数组长度为
n、总和为S、最大值为M。
- 时间复杂度：$O(n(1 + \log(S-M+1)))$。初始扫描是 $O(n)$，之后每个二分候选值都要用 $O(n)$ 做一次贪心判定。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 「最大值最小化」常可转成判定问题，再对具有单调性的答案域二分。
- 搜索边界不是经验值：最大元素是必要下界，总和是必然可行的上界。
- 贪心必须给出最少段数；其依据是每一刀都推迟到不能再放的位置。
- 判定使用“不超过
k段”，非负数组下可以继续拆成恰好k段。
易错点总结
[!yellow]
- 在数组下标上二分：本题单调的是候选段和，不是切点位置。
- 可行时令
right = mid - 1：mid可能正是第一个可行值，不能排除。- 不可行时令
left = mid：向下取整时区间可能不再缩小，导致死循环。- 新开一段时忘记令
sum = num：当前元素会丢失，段数被低估。- 要求贪心结果必须等于
k：少于k段仍然可行，可以继续拆分。- 排序后再分段：会破坏子数组必须连续且保持原顺序的约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1011. 在 D 天内送达包裹的能力 | 中等 | 同样二分最小容量并贪心统计连续分组数，运输题按天分段，本题按子数组分段。 |
| 875. 爱吃香蕉的珂珂 | 中等 | 同样将最优化转成单调可行性判定，本题控制每组和上限，原题控制处理速度。 |