LeetCode 410困难二分答案 · 贪心判定
分割数组的最大值 图解题解
这道题到底在问什么
给一个非负整数数组 nums 和整数 k，把它分成 k 个连续子数组，使得这 k 段各自和当中最大的那个尽可能小，返回这个最小化的最大值。
- nums
- [7,2,5,10,8]
- k
- 2
- 输出
- 18
先想最直接的笨办法
直接枚举每一种切法、算每种的最大段和再取最小——切法数量是组合级的，n=1000、k=50 时根本算不完。得换个思路。（动画第 3 步）
最优解：一步一步想明白
- 3直接枚举每一种切法、算每种的最大段和再取最小——切法数量是组合级的，n=1000、k=50 时根本算不完。得换个思路。
- 4关键翻转：不枚举怎么切，而是猜一个上限 cap。「最大段和 ≤ cap 是否可行」对 cap 是单调的——cap 越大越容易满足。于是答案落在一条单调线上，可以二分。
- 5怎么判一个 cap 行不行？能塞就塞、塞不下就切，贪心地用最少的段数装完。最后段数 ≤ k → cap 可行(段数少了把某段再切开总行)；段数 > k → cap 太小、装不下。下面盯住 cap、当前段和、段数怎么动。
- 6lo = max(nums) = 10cap 的下界：再怎么切，最大的那个数 10 总得单独待在某段里，所以 cap 不可能小于 10。lo 从 10 起。
- 7hi = sum(nums) = 32cap 的上界：极端情况只切 1 段(k=1)，那段和就是全部之和 32。所以答案一定落在 [10, 32] 这个区间里，接下来在它上面二分。
- 8mid = (10+32)/2 = 21第一轮取中点 mid = 21，意思是「假设最大段和不超过 21，够不够 2 段装完?」。下面贪心地从左往右塞一遍。
- 9段1: cur = 7 ┆ 段数 = 1从第一个数 7 开始：当前段和 cur = 7，没超过 cap=21，装进段1。绿色表示已经在当前段里。
- 10段1: cur = 9 ┆ 段数 = 1再塞 2，cur = 9，仍 ≤ 21，继续留在段1。
- 11段1: cur = 14 ┆ 段数 = 1塞 5，cur = 14，还没满。段1 现在是 [7,2,5]，和 14。
- 1214+10=24 > 21 ┆ 另起段2到 10 时 14+10 = 24 超过 cap=21，当前段塞不下了 → 在这里切一刀，把 10 放进新的段2，段数变成 2。前面的段1 已封口(变灰)。
- 13段2: cur = 18 ┆ 段数 = 2最后塞 8，段2 的 cur = 18 ≤ 21，装得下。扫完全部，一共切出 2 段：[7,2,5] 和 [10,8]。
- 14段数 2 ≤ k=2 ✓ ┆ hi = 21段数 2 正好 ≤ k=2，cap=21 可行!但我们要的是「最小的可行 cap」，所以把上界收到 hi=21，继续往小里试。区间变成 [10, 21]。
- 15mid = (10+21)/2 = 15新区间 [10, 21] 取中点 mid = 15，试更紧的 cap=15。再贪心扫一遍。
- 16cur = 14 ┆ 段数 = 17、2、5 一路塞进段1，cur = 14，刚好 ≤ 15。和上一轮一样，段1 还是 [7,2,5]。
- 1714+10=24 > 15 ┆ 段2 起10 又塞不下(24 > 15)，切一刀，段2 = [10]，段数到 2。
- 1810+8=18 > 15 ┆ 段3 起这回到 8 时，段2 的 10+8 = 18 也超了，又得切一刀，8 单独成段3。cap 太小，逼出了 3 段。
- 19段数 3 > k=2 ✗ ┆ lo = 16段数 3 > k=2，cap=15 太小、不可行。说明答案至少比 15 大，把下界抬到 lo = 16。区间变成 [16, 21]。
- 20mid = (16+21)/2 = 18区间 [16, 21] 取中点 mid = 18，试 cap=18。
- 21cur = 14 ┆ 段数 = 17、2、5 进段1，cur = 14 ≤ 18。
- 2214+10=24 > 18 ┆ 段2 起10 塞不下(24 > 18)，切，段2 = [10]，段数 2。
- 23段2: cur = 18 ┆ 段数 = 28 进段2，cur = 18，恰好等于 cap=18(等于也算装得下)。扫完 2 段，cap=18 可行。
- 24段数 2 ≤ k=2 ✓ ┆ hi = 18段数 2 ≤ k，cap=18 可行，hi 收到 18。区间只剩 [16, 18]，还能再挤吗?再来一轮。
- 25mid = (16+18)/2 = 17区间 [16, 18] 取中点 mid = 17，试比 18 更小的 cap=17，看能不能再省。
- 26[7,2,5] | [10] | [8] ┆ 段数 = 3cap=17 时和 cap=15 一样：[7,2,5] 后切，[10] 后 10+8=18 又超 17 再切，逼出 3 段。不可行，lo 抬到 mid+1 = 18。
- 27lo = hi = 18，停！lo 和 hi 都到了 18，二分停下。18 就是最小的可行 cap——也就是最优切法下那个「最大段和」。
- 28[7,2,5] 和 [10,8]，最大段和 = 18用 cap=18 落刀，切成 [7,2,5] 和 [10,8]，两段和 14 与 18，最大就是 18。和题目答案一致，搞定。
- 33「二分答案」是一类大套路：当「最优值」不好直接求、但「某个值行不行」好判且单调时，就二分这个值本身。LC1011 在 D 天内送达、LC875 吃香蕉速度都是同一招。
⚠️ 容易写错的地方
✗ 错：lo 初值写成 0 或 1
✓ 对：lo = max(nums)
cap 必须装得下最大单值，否则那个数永远切不进任何段
✗ 错：判定写成 cnt == k
✓ 对：用 cnt <= k
段数比 k 少没关系(再把某段切开就凑到 k)，关键是不能超
✗ 错：求和用 int 溢出
✓ 对：sum 用 long
n、值都大时 sum 会超过 int 范围，C++/Java 必须用 long
完整代码（Python / C++ / Java）
Python
class Solution:
def splitArray(self, nums, k):
def can(cap): # 贪心: cap 下最少切几段
cnt, cur = 1, 0
for v in nums:
if cur + v > cap: # 塞不下 → 另起一段
cnt += 1
cur = v
else:
cur += v
return cnt <= k # 段数 ≤ k 即可行
lo, hi = max(nums), sum(nums) # 答案区间
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # 可行 → 收紧上界
else:
lo = mid + 1 # 不可行 → 抬高下界
return loC++
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
long lo = 0, hi = 0;
for (int v : nums) { lo = max(lo, (long)v); hi += v; }
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (can(nums, k, mid)) hi = mid; // 可行 → 收紧
else lo = mid + 1; // 不可行 → 抬高
}
return (int)lo;
}
bool can(vector<int>& nums, int k, long cap) {
int cnt = 1; long cur = 0;
for (int v : nums) {
if (cur + v > cap) { cnt++; cur = v; } // 切
else cur += v;
}
return cnt <= k;
}
};Java
class Solution {
public int splitArray(int[] nums, int k) {
long lo = 0, hi = 0;
for (int v : nums) { lo = Math.max(lo, v); hi += v; }
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (can(nums, k, mid)) hi = mid; // 可行 → 收紧
else lo = mid + 1; // 不可行 → 抬高
}
return (int) lo;
}
private boolean can(int[] nums, int k, long cap) {
int cnt = 1;
long cur = 0;
for (int v : nums) {
if (cur + v > cap) { cnt++; cur = v; } // 切
else cur += v;
}
return cnt <= k;
}
}复杂度
时间复杂度
O(n · log(sum−max))
二分答案区间 O(log(sum−max)) 次，每次贪心扫一遍 O(n)
空间复杂度
O(1)
只用 lo/hi/mid 和贪心里的 cur/cnt 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分割数组的最大值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么对 cap 二分是对的(单调性在哪)？+
cap 越大，每段能装越多，需要的段数越少;所以「段数 ≤ k」随 cap 增大从「假」变「真」且不再变回，是单调的，可以二分这个分界点。
和动态规划解法比怎么样？+
DP 解法 dp[i][j] 把前 i 个数分 j 段的最优值，复杂度 O(n²·k)，n 大时偏慢;二分答案 O(n·log(sum)) 更快更省内存，是这题的首选。
数组含 0 或负数会怎样？+
本题非负。若含负数，可行性对 cap 不再单调(加负数反而能减小段和)，二分答案失效，得退回 DP。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 分割数组的最大值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。