LeetCode 410. 分割数组的最大值
目录
题目描述
题意分析
输入是一个非负整数数组和一个正整数
k，要求把数组切成恰好k段。「段」的含义被限定得很死：每一段都是原数组里一段连续的元素，不能跳着挑，也不能重排顺序，并且每段都不能为空。要输出的不是某种切法，而是一个数值：在所有合法切法里，把「各段和的最大值」这个指标取到最小时，那个最小值是多少。换句话说，评价一种切法好坏的标准，只看它最重的那一段有多重；我们要找的是「最重的一段」尽可能轻的方案。
约束里有两条信号值得注意。第一，元素都是非负数，这意味着往一段里继续塞元素，段和只会增不会减，「装不下就换一段」这种朴素判断才是可靠的。第二，数据规模上数组长度上千、元素值上百万，总和量级在 $10^9$ 以内，用
int存总和不会溢出，但按「切法」枚举显然是天文数字。边界情况也要想清楚。
k等于1时只有一段，答案就是总和；k等于数组长度时每个元素独占一段，答案就是数组最大值。这两个极端顺带说明了答案的取值范围：不可能小于数组最大值（那个元素总要落在某一段里），也不可能大于总和。
解法：二分答案 + 贪心判定
核心思路
直接枚举切点或使用区间 DP 都较重。更适合面试的做法是二分「最大子数组和」这个答案。
答案下界是数组最大值
max(nums)，因为任何元素都必须属于某一段；上界是数组总和sum(nums)，因为把全部元素放进一段一定可行。对候选上限
limit，从左到右贪心分段：当前元素还能放进本段就继续放，超过limit才新开一段。这个策略让每一段都尽量向右延伸。任意合法方案的第一刀都不可能比贪心更靠右；去掉第一段后同理，因此贪心得到的是该上限下的最少段数。可行性定义为「最少段数不超过
k」。由于元素非负，如果能分成少于k段，还可以继续拆分非空段，直到恰好k段，最大段和不会增加。于是它与题目的“恰好k段”等价。
limit越大，需要的段数只会更少，因此可行性呈现“前面不可行、后面可行”的单调结构。二分找到第一个可行的limit，就是最小化后的答案。循环始终保证答案位于闭区间[left, right]中。
解题步骤
- 扫描数组，令
left = max(nums)、right = sum(nums)。- 当
left < right时，取mid = left + (right - left) / 2。- 用贪心检查
mid：累加当前段，若加入num后超过mid，就以num开启新段。- 若段数不超过
k，mid可行，令right = mid；否则令left = mid + 1。- 当区间收敛时返回
left。对
[7, 2, 5, 10, 8]、k = 2，初始区间是[10, 32]。候选值依次为21（可行）、15（不可行）、18（可行）、17（不可行），最终收敛到18，对应[7,2,5]与[10,8]。
代码实现
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)$。
关键点总结
- 「最大值最小化」常可转成判定问题，再对具有单调性的答案域二分。
- 搜索边界不是经验值：最大元素是必要下界，总和是必然可行的上界。
- 贪心必须给出最少段数；其依据是每一刀都推迟到不能再放的位置。
- 判定使用“不超过
k段”，非负数组下可以继续拆成恰好k段。
易错点总结
- 在数组下标上二分：本题单调的是候选段和，不是切点位置。
- 可行时令
right = mid - 1：mid可能正是第一个可行值，不能排除。- 不可行时令
left = mid：向下取整时区间可能不再缩小，导致死循环。- 新开一段时忘记令
sum = num：当前元素会丢失，段数被低估。- 要求贪心结果必须等于
k：少于k段仍然可行，可以继续拆分。- 排序后再分段：会破坏子数组必须连续且保持原顺序的约束。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 69. x 的平方根 | 简单 | 判定只需一次乘法，不涉及数组扫描 |
| 644. 子数组最大平均数 II | 困难 | 二分实数而非整数，判定要靠前缀和找非负区间 |
| 668. 乘法表中第k小的数 | 困难 | 二分的是「第 k 小」，判定按行统计个数而非分段 |
| 719. 找出第 K 小的数对距离 | 困难 | 判定用双指针统计数对，需先排序 |
| 774. 最小化去加油站的最大距离 | 困难 | 实数二分且判定是「新增多少个点」而非「切成多少段」 |
| 875. 爱吃香蕉的珂珂 | 中等 | 分组由堆数固定，判定是向上取整求和 |
| 878. 第 N 个神奇数字 | 困难 | 判定用容斥与最小公倍数计数，还要取模 |
| 1011. 在 D 天内送达包裹的能力 | 中等 | 与本题几乎同构，只是段和换成载重、段数换成天数 |
| 1201. 丑数 III | 中等 | 判定是三个数的容斥计数，需要防乘法溢出 |
| 1231. 分享巧克力 | 困难 | 求「最小段和最大」，贪心方向与本题相反 |
| 1482. 制作 m 束花所需的最少天数 | 中等 | 二分的是天数，判定要数连续可用段的长度 |
| 1552. 两球之间的磁力 | 中等 | 最小间距最大化，判定是贪心放球计数 |
| LCP 12. 小张刷题计划 | 中等 | 分段时允许免费跳过段内最大值，贪心多一层决策 |
| LCR 072. x 的平方根 | 简单 | 单调函数求整数根，需处理平方溢出 |
| LCR 073. 爱吃香蕉的狒狒 | 中等 | 上界取最大堆而非总和，判定按堆独立计算 |
| 补充题 7. 木头切割问题 | 中等 | 判定用整除累加根数，段长可自由取而非受连续限制 |
| 补充题 20. 立方根 | 中等 | 实数二分，收敛条件靠精度阈值而非区间相等 |