“分组”这两个字一出现在题目名里十有八九是在考你有秩序地做决策。今天要写的这道题我在刷题群里看人问过好几遍给你一个数组要求按顺序切成恰好 k 段让所有段的和里面最大的那个尽可能小。拿到题第一反应可能是动态规划但这篇题解会告诉你更适合的解法是二分答案加贪心判定——这也是整个“最小化最大值”题型的地基。适合谁看刚开始练二分的同学、准备算法面试的开发者还适合那些写 check 函数时总差一个等号的倒霉蛋我承认我也曾是。不需要复杂的数学数组非负思路直观代码二三十行就能收工。下面从题目拆解开始把每一步为什么这么走都讲清楚。1. 先把“分组”翻译成人话1.1 题意还原与样例题目长这样给定一个长度为 n 的非负整数数组 nums以及一个正整数 k要求把数组按原有顺序切成恰好 k 段连续子数组每段非空然后计算这 k 段各自的和。希望这 k 个和中的最大值尽量小输出那个最小的“最大段和”。光看定义有点绕我们用一组数据走一遍。假设nums [7, 2, 5, 10, 8]k 2可以切成 [7, 2, 5] 和 [10, 8]两段和分别是 14 和 18最大值为 18。也可以切成 [7, 2] 和 [5, 10, 8]两段和是 9 和 23最大值是 23。还可以切成 [7] 和 [2, 5, 10, 8]最大值是 25。比较下来18 就是所有切法里“最大段和”最小的那个答案输出 18。这个例子很经典因为它会出现“单段和很大但另一段很小”的极端情况逼着你思考怎样把负载摊匀。注意一个关键点题目说的是“连续子数组”也就是切完之后段与段之间不能交换元素顺序更不能把元素挑出来重新组合。这个约束决定了后面整套算法方向。1.2 连续与非连续的天壤之别同样是“分组”连续与不连续是两个物种。如果允许打乱顺序再分组那问题就变成类似“把 n 个数装进 k 个袋子让最重的袋子尽量轻”。那种题往往用贪心加最大堆每次把当前最大的数塞进当前总和最小的袋子里思路完全是另一套。但本题要求保持顺序实际上就是你在原数组上插 k-1 把“剪刀”剪刀之间不能交叉切完的每一段保持原样。这个连续性假设在现实生活中非常常见。你想想生产排程一批订单必须按照先后顺序在一条流水线上加工你想把它们分成 k 个批次每个批次的加工时长不能差太多这就是连续分组。日志系统按时间顺序落盘要切成 k 个文件分片也不可能把后面的日志插到前面去。所以题目不是故意刁难你它模拟的是很实际的约束顺序不能乱负载要均衡。1.3 为什么暴力切分想都不用想n 个数切成 k 段相当于在 n-1 个空隙里选 k-1 个位置下刀组合数是 C(n-1, k-1)。当 n30、k15 时这个数已经超过 7700 万n 到 100 的时候就彻底爆掉了。所以暴力枚举切点这条路第一秒就可以放弃。剩下两条路动态规划或者二分答案加贪心判定。两条路都能解但适用场景和复杂度差别很大。动态规划是“正面硬刚”把状态定义成“前 i 个数分成 j 段的最优值”思路很直观但朴素转移是 O(k n^2)遇到 n10^5 直接超时。二分答案则是“曲线救国”不直接找最优切法而是先猜一个答案 X再检查“能不能用不超过 k 段让每段和都不超过 X”。这个检查过程是 O(n) 的而二分只需要 log(总和) 轮整体 O(n log n) 级别跑起来舒服得多。我个人的判断习惯是看到“最大值最小”或者“最小值最大”这种字眼先在心里给二分答案记一笔。它大概率不是唯一解但往往是性价比最高的解。2. 二分答案 贪心这道题的最短路径2.1 换一个问法给你一个上限 X二分答案的核心思想是把“求最优值”改成“判可行性”。原问题问的是最优的最大段和是多少现在换成我随便给定一个数 X你告诉我有多少种切法能保证每一段的和都不超过 X。举例来说nums [7, 2, 5, 10, 8]k 2。如果 X 15能不能切成至多 2 段每段和都不超过 15试试看第一段从 7 开始加 2 得 9再加 5 得 14再加 10 就成 24 超了所以第一段只能到 [7, 2, 5]。第二段从 10 开始加 8 得 18也超了 15所以第二段只能是 [10]第三段 [8]。切出来是 3 段超过 k2说明 X15 不可行。如果 X 18第一段 [7, 2, 5] 和是 14没超第二段 [10, 8] 和是 18刚好等于 X两段搞定可行。所以这个例子中答案在 16 到 18 之间的某个位置。至于为什么最终是 18 不是 17可以自己拿 17 试一遍会发现无论如何都要切成 3 段。这样一来问题就从“找出最优切法”变成了“判断 X 是否可行”。而“判断”这件事比“求解”简单太多因为我们可以用很粗暴的贪心策略。2.2 单调性二分合法的底气二分能工作的前提是答案具备单调性。这里非常明显X 越大每段能装的东西越多需要切出的段数只会越少X 越小段数只会越多。所以“X 可行”这个属性是单调的一旦 X 可行那么所有比 X 大的数一定也可行一旦 X 不可行所有比 X 小的数一定也不可行。用一句人话说可行性函数是一个只有 false 和 true 两段的阶梯左边全是 false右边全是 true我们要找的是 true 区域最左边那个点。这就是二分的标准适用场景。上界和下界也好定。下界不能比数组里最大的单个元素小因为无论怎么切那个最大的元素自己所在的那一段和至少等于它本身。所以下界 L max(nums)。上界可以是 sum(nums)因为当 X 等于总和时不分段就是一段段和等于总和一定可行。这样搜索区间 [L, R] 就是 [max(nums), sum(nums)]宽度非常合理不会做无用功。2.3 check 函数里的贪心为什么敢这么写判断 X 是否可行的 check 函数写法极其简单从左往右扫描数组累加当前段的和如果加上下一个元素会超过 X就在这里切一刀新段从下一个元素开始。这个贪心的核心逻辑是每一段尽量装到不能再装为止。为什么这种“撑满”策略是对的因为它能保证切出来的段数是最少的。想一个反证假设存在一种更优的切法总段数比贪心切出来的还少。既然贪心每一段都撑到了极限那么任何其他切法必然存在某个位置贪心把元素装进了前一段而更优切法却在这里提前下刀了。提前下刀意味着前一段少装了一些元素而后一段多装了一些。如果把那个元素从后一段挪回前一段前一段的和依然不超过 X因为贪心当初就允许它装进来后一段的和变小了当然也不超过 X。于是我们得到一个段数相同甚至更少的新切法。反复执行这个调整最终可以变成贪心切法说明贪心切法的段数不会比任何切法多。用人话说就是你都把每段塞到最满了不可能还有办法切出更少的段数。所以 check 函数只需统计贪心切法用了多少段如果段数不超过 k说明 X 可行否则不可行。这里有个细节值得强调题目要求“恰好 k 段”而 check 判断的是“不超过 k 段”。两者等价吗等价的前提是 k n 且每段非空。因为如果你用少于 k 段就满足了每段和不超过 X只需要把其中某一段再拆开拆出来的两段和等于原段和依然不超过 X段数就增加了可以一直加到恰好 k 段。所以“至多 k 段可行”与“恰好 k 段可行”在这个题设下是一回事。很多教程不点破这一点导致有人写 check 时对段数到底用 还是 纠结老半天。3. 代码怎么落地才不容易写崩3.1 C 参考实现思路理清了代码其实很短。先看 C 版本我带着注释写一遍#include bits/stdc.h using namespace std; typedef long long ll; // 判断在每段和不超过 limit 的前提下能否用不超过 k 段分完 bool check(const vectorint nums, int k, ll limit) { ll cur 0; // 当前这一段已经累加的和 int cnt 1; // 当前已经用了多少段先默认有第一段 for (int x : nums) { if (x limit) return false; // 单个元素就超限谁来了都不行 if (cur x limit) { cnt; // 当前段加不下 x必须开新段 cur x; // 新段从 x 开始 if (cnt k) return false; // 段数超了提前退出 } else { cur x; } } return cnt k; } int splitArray(vectorint nums, int k) { ll left 0, right 0; for (int x : nums) { right x; if (x left) left x; // left 至少是最大单元素 } if (k nums.size()) return -1; // 不可能切成超过元素个数的非空段 while (left right) { ll mid left (right - left) / 2; if (check(nums, k, mid)) { right mid; // mid 可行答案不会比 mid 更大 } else { left mid 1; // mid 不可行答案一定比 mid 大 } } return left; }几个细节我特别说一下。cnt初始化为 1 而不是 0是因为扫描第一个元素时还没有“开新段”的动作但已经在第一段里了。如果你把cnt初始化成 0后面计数逻辑就得在每个元素处都判断是否开段容易乱。left初始化为max(nums)而不是 0能直接砍掉一段无效二分区间。因为答案不可能小于最大元素从最大元素开始找是安全的。mid用left (right - left) / 2而不是(left right) / 2防止两个大数相加溢出。虽然这里 left 和 right 都是 long long没那么容易爆但养成这个习惯没坏处。3.2 Python 参考实现Python 写起来更短思路完全一样def check(nums, k, limit): cnt 1 cur 0 for x in nums: if x limit: return False if cur x limit: cnt 1 cur x if cnt k: return False else: cur x return cnt k def split_array(nums, k): left, right max(nums), sum(nums) while left right: mid (left right) // 2 if check(nums, k, mid): right mid else: left mid 1 return leftPython 的整型不会溢出所以 mid 直接写(left right) // 2也没问题。只不过 Python 在 n 特别大的时候遍历本身的常数比较大如果卡性能可以考虑用 PyPy 跑。竞赛场合用 Python 写这种题基本没压力因为 O(n log sum) 的复杂度不高。3.3 边界、溢出和初始化细节这道题最容易翻车的不是算法而是边界。第一数据类型。题目只给非负整数但数组长度可能到 10^5单个元素可能到 10^9总和能到 10^14 这个量级。用 int 存 sum 和 limit 必炸C 一定要开 long long。别觉得样例能过就万事大吉样例数据通常温和得骗人。第二k 和 n 的关系。如果 k n不可能切出恰好 k 个非空段直接输出 -1 或者按题目要求处理。有些题目没给这种非法数据但你自己心里要有数。遍历的时候如果 cnt 已经超过 k提前返回 false能省一点时间也避免后续无意义的累加。第三空数组。如果 nums 为空那答案是多少不同题目定义不一样。大多数分组题默认 n 1但如果你写通用函数最好在开头加个判断空数组时按题意通常返回 0。否则left max(nums)会直接报错。第四check 里x limit的判断不能省。我见过有人觉得反正cur x limit时 x 也会被单独开段于是不写这个判断。但会出现一个隐蔽 bug如果单个 x 已经大于 limit你会把它放进一个新段cur 变成 x这个 cur 本身就已经超限了后面再遇到别的元素又会错误地继续比较。更糟的是如果 k 恰好很大这个错误状态可能被 cnt k 兜住返回一个错误的 true。所以单个元素超限直接返回 false是最干净的处理。4. 调试实录那些 WA 到怀疑人生的地方4.1 边界样例对照表写代码之前先把边界样例准备好。我刷题习惯用一张小表做自测每种边界跑一遍能过滤掉八成低级错误。这道题我常用的测试用例长这样输入k期望输出说明[1, 2, 3, 4, 5]115只能一段直接总和[5, 5, 5, 5, 5]55每段一个元素最大段和就是 5[1, 1000000000]11000000000大数int 会溢出[7, 2, 5, 10, 8]218标准样例[10, 20, 30, 40, 50]290切 [10,20,30] 与 [40,50][3, 3, 3, 3, 3]46切 [3,3] 和三个 [3] 之类用这些数据跑一遍基本能保证主流程是对的。真正难的往往是后面几种边界组合比如“k 恰好等于 n”时答案就是 max(nums)而二分法也会正确收敛到 max(nums)。4.2 二分模板千万不能混二分模板是重灾区。天天有人把left right、left right、right mid、right mid - 1混着写结果不是死循环就是答案偏一位。我长期用的模板是左闭右闭的“寻找第一个可行值”while (left right) { mid left (right - left) / 2; if (check(mid)) right mid; else left mid 1; }这个模板的逻辑是每次循环都保证答案在 [left, right] 区间里。如果 mid 可行说明答案 mid所以把右边界收到 mid如果 mid 不可行说明答案 mid所以把左边界收到 mid 1。循环结束时 left 和 right 相等就是答案。关键点在于mid 可行时right mid不要写right mid - 1。因为你不能排除 mid 本身就是答案的情况。一旦写成right mid - 1答案就被排除在搜索区间外了最后必然出错。同理不可行时left mid 1不要写left mid否则当 left 和 right 相邻时会死循环left17, right18, mid17check(17) 为 falseleft 仍然是 17永远跳不出去。还有一个小习惯如果你用的是mid (left right 1) / 2这种上取整写法通常是配合“寻找最后一个可行值”用的。不要在同一道题里来回切模板选一个背熟比背十个半生不熟强得多。4.3 段数统计的初始化陷阱再讲一个我实际踩过的坑cnt 到底是 0 还是 1。如果你把 cnt 初始化为 0用“遇到超限就 cnt然后 cur x”的逻辑跑完循环后总段数是 cnt 1因为最后一个段在循环结束时没有触发计数。很多人忘了最后这个 1导致 check 返回的段数少 1恰好错的又不多样例还容易过非常阴险。我建议用 cnt 1 的写法循环里每开一个新区段才 cnt这样循环结束时 cnt 就是真实段数不需要额外修正。写 check 函数时先搞清楚“当前这一段的归属”比硬套公式要可靠。4.4 一个更隐蔽的错误恰好 k 段与至多 k 段的等价条件上文说了当每段非空且 k n 时“至多 k 段可行”等于“恰好 k 段可行”。但如果你把题设改一改比如要求“每一段至少包含两个元素”这个等价关系就不成立了。因为有时候你少切几段可以满足和的上限但把段继续拆开时可能拆不出“每段至少两个元素”的合法切法。所以不要把这个等价条件背成铁律要理解它依赖的前提段可以无条件继续拆分。竞赛里大多数连续分组题都满足这个前提所以 check 里用cnt k是对的。但面试时如果面试官加一句“每段长度不能超过 3”你就要重新审视 check 的写法了。5. 分组题的亲戚们DP、变体和选型5.1 动态规划思路对照二分答案不是唯一解法。如果你看到这道题第一反应是 DP说明你状态定义的基本功不错。DP 写法是这样的设 dp[i][j] 表示把前 i 个元素分成 j 段时最小的“最大段和”。转移时枚举最后一段的起点 t那么dp[i][j] min( max(dp[t][j-1], sum(t1...i)) )其中 t 的取值范围是 j-1 到 i-1。边界条件是 dp[0][0] 0dp[i][0] 正无穷除 dp[0][0] 外。答案就是 dp[n][k]。这种做法能理解题目的结构但对 n 和 k 都很大的情况就无能为力了。复杂度是 O(k n^2)n5000 基本到头。所以如果题目给了大的 nDP 只能用来对拍验证二分答案的正确性。我经常写一个暴力 DP 和一个二分答案随机生成小数据对比输出确认二分写对了再删掉 DP 提交。这个“对拍”习惯帮我抓出过好几个边界 bug。5.2 分组背包别和这道题搞混“分组”这个词在算法里还有另一个常见含义分组背包。分组背包的问题是给你若干组物品每组里最多选一个放进容量有限的背包求最大价值。它和这道题完全是两码事唯一的共同点是名字里带“分组”二字。分组背包的决策维度是“每组选哪个”不要求物品连续也不涉及段和均衡。如果你在准备面试时把两个题混在一起复习会很混乱。我的建议是看到“连续子数组”“切成 k 段”这种描述立刻归到数组分段问题看到“每组选一个”“每组最多取一个”立刻归到背包 DP。两条路线互不交叉。5.3 几个常见变体至多 k 段、求具体方案、非负改负数这道题的变体非常多换一个条件解法就要跟着调整。第一个变体把“恰好 k 段”改成“至多 k 段”。这个最简单check 函数里cnt k的语义本来就是“至多”所以二分的主流程完全不用改题目可能还会给你一个更宽松的答案范围。第二个变体要求输出具体切法而不只是答案。二分答案算出最优 X 之后可以再跑一遍 check并在每次切段时记录切点位置。这里要注意如果要输出的是“恰好 k 段”的方案而二分过程只能保证“至多 k 段”你就需要在记录切点时额外处理如果贪心切出来的段数小于 k把其中某些段继续拆开补足段数。具体拆哪一段拆任何一段都行只要保证每段非空即可。这个补段逻辑容易写乱我的建议是先按贪心切得到少段方案再按顺序把每个可拆的段从末尾拆开直到段数达到 k。第三个变体数组里有负数。这就要命了。一旦允许负数“每段尽量撑满”的贪心不再成立因为多加一个负数可能会让段和变小从而可能导致更少的段数。此时二分答案加贪心的基础就崩塌了必须回到 DP。好在竞赛里这种题很少见面试也基本不会考但你需要知道这个边界在哪里。5.4 什么时候无脑二分什么时候老老实实 DP我自己的选型标准很简单数组非负、要求连续分段、目标是最大化或最小化某个段相关值 → 优先想二分答案 贪心。数组有负数、段数限制很小、需要求方案数 → 想 DP。题目明确要求输出所有可行方案 → 想搜索或 DP 回溯。二分答案的最大优势是 O(n log V) 的复杂度对数据范围非常宽容check 函数又简单到不容易写错。它最大的劣势是只能给出答案值不能直接给出方案。如果题目既要你求值又要你构造方案那就先二分求值再基于这个值重新构造。6. 一点题外话优化问题向判定问题的转换我个人在实际刷题中的体会是二分答案这层“转换”比任何模板都值钱。你看到的每个“最大值最小”题本质上都是一个优化问题在巨大的决策空间里找一个最优值。直接搜决策空间往往爆炸但如果能把目标值 X 拿在手里反问一句“给定 X可行吗”问题规模就瞬间塌缩成一个简单判定。这就像找一条路的最窄处。你不知道最窄处到底多窄但你可以先假设一个宽度 X然后沿着路走一遍看能不能不碰到路肩走完全程。能走通就说明真实最窄处不大于 X走不通就说明大于 X。反复猜指数级逼近正确答案。这个思路不只在算法题里有用。我自己做项目排期时也会用假设一个总工期反过来检查每个任务能不能塞进这个工期里不行就放宽行就收紧。工具不同思维一模一样。最后再分享一个小技巧写分组题时先把 check 函数单独拿出来测用几组手工数据验证“X0 永远 falseXsum 永远是 trueXmax 有时 false 有时 true”确认 check 没问题后再开始调二分。很多人一上来就在二分循环里 debug问题是 check 的 bug 会被二分循环放大错误信息层层包裹越查越晕。分层测试一次只信一个函数能省下大量时间。