刷题的朋友对 LC410 应该不陌生它常年活跃在各种算法清单的“必做经典”里标签就是标题里这七个字贪心 二分答案。我第一次做这题的时候其实被“分割数组的最大值”这个拗口的提法绕晕了后来才意识到它就是一个典型的“最大值最小化”问题——遇到这种描述十有八九跟二分答案脱不了干系。这篇文章就围绕 LC410 展开把贪心怎么配合二分、边界怎么卡、常见坑怎么躲一次说清楚。不管你是刚接触二分的入门选手还是想系统整理套路准备面试这篇都能帮你省下不少时间。1. 读懂题目把一个“直觉问题”翻译成可计算的模型1.1 题目到底在问什么题面本身不复杂给你一个非负整数数组nums再给一个整数m要求把数组分成m 个非空的连续子数组然后让这 m 个子数组各自的和的最大值尽可能小。注意关键词是“连续”。不是让你挑元素、重排而是沿着数组切 m-1 刀切成 m 段。每段内部元素在原数组里是相邻的段与段之间不能有重合也不能有遗漏。最后的目标函数是所有段和中那个最大的值要让它最小。我一般会用生活化的类比来理解它你有一长排货物每个货物的重量是nums[i]现在要把它们按顺序装箱正好装 m 箱请问每箱最大承重至少要设计成多少才能保证装得下同时又不浪费注意“按顺序”是硬约束你不能为了平衡而乱序——现实里的流水线装箱也是这个逻辑。这个题目之所以值得反复咀嚼是因为它把“最优化”和“可行性验证”揉在一起考查。直接想到底怎么切才能让最大段和最小暴力枚举所有切法的复杂度是指数级nums长度稍微一上去就彻底爆炸。所以我们需要换一种思考方式把“求最优”变成“猜答案再验证”。1.2 边界条件和易踩坑点动手写代码前先把边界情况盘一遍省的后面被隐藏用例坑哭。m的范围是1 m nums.length所以不可能出现“段数比元素个数还多”的非法输入。数组元素是非负整数这一点非常重要。正因为非负子数组的和才是单调递增的后面贪心验证才成立。如果数组里有负数这个题的贪心逻辑就要全部重写因为“加了负数反而更小”会破坏连续性策略。每段必须非空。这意味着切分的时候至少要保证每个段里至少有一个元素不能出现“新增一段但当前段还是空的”这种情况。单个元素的值可能很大整个数组的和可能更大。所以中间计算建议用long long不然right直接取sum(nums)在极端用例下会溢出int。这些边界看起来琐碎但在面试里往往是区分“会做”和“做对”的分水岭。2. 为什么是二分答案从“求最优值”到“验证可行性”的思考转换2.1 直接求最优很难但验证一个值行不行很简单先抛一个问题给你一个猜测的容量x让你判断“能不能把数组分成不超过 m 段且每段的和都小于等于 x”。这个问题的难度和原题完全不是一个量级的。验证过程非常直接从前往后扫用一个变量累加当前段的和。如果累加到某个元素后和超过了x说明当前段装不下了那就从这里切开新开一段并把这个元素作为新段的第一件“货物”。如果整个数组扫描完开出的段数不超过m说明“容量 x 够用”否则说明x太小装不下。这个过程就是典型的贪心每次都尽可能往当前段里塞塞不下才开新段。你可能会问这样的局部最优能保证全局最优吗答案是能而且原因很简单——所有元素都是非负的。在容量固定为x的前提下段越多段和越容易变小但我们的目标是段数尽量少所以“能塞就塞”的策略得到的段数一定是最少的。有了这个快速验证的能力原问题就被转换成了找到一个最小的x使得验证通过。2.2 单调性是二分的灵魂为什么可以用二分而不是别的搜索方式因为验证结果关于x是单调的如果某个容量x可以成功段数不超过 m那么比x更大的容量也一定可以成功。容量大了每段能装更多段数只会更少。反过来如果某个容量x失败段数超过了 m那么比x更小的容量也一定失败。容量小了每段能装的更少段数只会更多。这就是典型的“可行域是连续区间”的特征二分可以直接在这个区间上寻找左端点。很多人问为什么这里的答案是“最大值最小”用二分找的是可行域的左边界而不是右边界我习惯这样记check(x)返回true表示“答案小于等于 x”。既然我们要找最小的那个可行值那就不断把右边界往左收最终left收敛到第一个可行的位置。2.3 上下界的确定参数计算逻辑二分的第一步是确定搜索空间也就是left和right的初始值。下界left不能取 0。因为任何一个子数组至少要包含一个元素所以“每段和最大值”不可能小于数组中最大的那个单元素。如果取left 0check(0)面对第一个正数元素就直接失败丢掉二分的正确性。所以正确写法是left max(nums)。上界right把所有元素放进同一段段和就是整个数组的和sum(nums)。这是最极限的“一段切法”所以答案是绝对不可能超过这个值的取right sum(nums)。搜索区间是[max(nums), sum(nums)]长度不算大但每次check都是 O(n) 扫描整体成本可控。这里的下界优化是很多人容易忽略的小细节严格来说取 0 也能二分出正确答案但会多做若干次无意义的check更重要的是从max(nums)开始二分你的思维是清晰的——你知道为什么每个候选答案都不可能低于这个下限。3. 贪心验证的核心逻辑与代码落地3.1 check 函数一步步拆解我们来把验证函数写细以 C 为例bool check(vectorint nums, int m, long long x) { int cnt 1; // 当前已用的段数初始至少为 1 long long cur 0; // 当前这段的累加和 for (int num : nums) { if (cur num x) { cnt; // 装不下了新开一段 cur num; // 新段从当前元素开始 if (cnt m) return false; // 段数超了提前剪枝 } else { cur num; // 还能装继续累加 } } return cnt m; }这里有两个关键细节新手最容易出错。第一为什么cnt的初始值是 1 而不是 0因为哪怕数组只有一个元素它也要属于某一段。我们在遍历时第一个元素一定是被“放进”第一段的——不管它后面有没有触发开新段的逻辑。所以段数从 1 开始计数逻辑上更贴合“已经存在一个当前段”的事实。第二cur num x时为什么cur要重置为num而不是 0因为当前这个元素必须被放进新的一段里它是新段的第一个元素。如果重置为 0下一轮循环再把num加进去功能上等价但多一次加法而且如果写成cur 0后忘记加下一个元素逻辑就崩了。直接赋值成num更直白。3.2 为什么段数少于 m 也没关系很多人验证的时候会写成return cnt m这是一个经典的错误。我当初也踩过这个坑后来想明白了其中的道理check(x)要回答的是“容量 x 是否够用”而不是“容量 x 是否恰好需要 m 段”。如果在x的容量下最少只需要 m-1 段就能装完那说明容量 x 是够的——因为我完全可以把其中一段再拆一刀比如把长度为 3 的一段拆成 12 两段每段的和只会更小依然小于等于 x。拆分的操作不会破坏“每段和不超过 x”这个约束。所以正确的判断条件是cnt m而不是cnt m。这个细节直接决定了正确性写成会漏掉大量可行答案导致二分最终结果偏大。3.3 与二分模板配合的细节有了check主函数只需要在这个单调区间上做标准二分即可int splitArray(vectorint nums, int m) { long long left 0, right 0; for (int num : nums) { left max(left, (long long)num); right num; } while (left right) { long long mid left (right - left) / 2; if (check(nums, m, mid)) { right mid; // 可行尝试更小的答案 } else { left mid 1; // 不可行答案必须更大 } } return (int)left; }这里的模板是“寻找左边界”的标准写法check(mid)为真说明mid可能是答案或者答案比它更小所以把右边界收到mid为假说明mid太小答案一定大于mid所以把左边界推进到mid 1。循环结束条件left right最终收敛点就是答案。mid left (right - left) / 2的写法比(left right) / 2更好虽然在这个题里 left 和 right 的值域不至于溢出但在面试里养成这个习惯能避免很多其他题目中的潜在溢出问题。4. 完整代码与复杂度分析4.1 两种语言的完整实现C 完整版本class Solution { public: int splitArray(vectorint nums, int m) { long long left 0, right 0; for (int num : nums) { left max(left, (long long)num); right num; } while (left right) { long long mid left (right - left) / 2; if (check(nums, m, mid)) { right mid; } else { left mid 1; } } return (int)left; } private: bool check(vectorint nums, int m, long long x) { int cnt 1; long long cur 0; for (int num : nums) { if (cur num x) { cnt; cur num; if (cnt m) return false; } else { cur num; } } return cnt m; } };Python 完整版本class Solution: def splitArray(self, nums: List[int], m: int) - int: def check(x: int) - bool: cnt 1 cur 0 for num in nums: if cur num x: cnt 1 cur num if cnt m: return False else: cur num return cnt m left, right max(nums), sum(nums) while left right: mid (left right) // 2 if check(mid): right mid else: left mid 1 return left两个版本逻辑完全一致Python 版本更简洁适合快速验证思路C 版本需要注意long long防止累加溢出。4.2 复杂度分析时间复杂度二分的区间长度是sum(nums) - max(nums)二分迭代次数为O(log(sum))每一次迭代都要调用check从头到尾扫描数组复杂度为O(n)所以总时间复杂度是O(n * log(sum))。空间复杂度check函数只用了几个变量没有额外数组空间复杂度是O(1)。这里要注意C 版本如果用vector做拷贝传参会多出 O(n) 的空间和拷贝时间所以一定要用引用传递const vectorint。对比一下暴力枚举和动态规划方案方案时间复杂度空间复杂度说明暴力枚举切法O(2^n)O(n)指数级完全不可用经典 DPO(n^2 * m)O(n * m)能过小数据大数组直接 TLE贪心 二分答案O(n * log(sum))O(1)主流正解简洁高效所以这道题的最优解不是更复杂的状态转移而是这种“猜答案 验证”的思辨方式这也是二分答案这类题型的魅力所在。4.3 用示例手动推演一遍拿题目的经典样例nums [7, 2, 5, 10, 8], m 2来手工模拟初始left max(nums) 10right sum(nums) 32。第一轮mid (10 32) / 2 21。check(21)扫描数组72514 没超再加 10 变成 24 超了开新段cur10加 8 变成 18没超。最终用了 2 段cnt 2成立所以答案不高于 21right 21。第二轮mid (10 21) / 2 15。check(15)72514 没超加 10 超了开段cur10加 8 变成 18 又超了再开段cur8。最终用了 3 段cnt 2失败所以答案必须大于 15left 16。第三轮mid (16 21) / 2 18。check(18)72514 没超加 10 变成 24 超了开段cur10加 8 变成 18没超。最终用了 2 段可行right 18。第四轮mid (16 18) / 2 17。check(17)72514 没超加 10 超了开段cur10加 8 变成 18 超了再开段。最终用了 3 段失败left 18。此时left right 18循环结束答案就是 18。整个过程逻辑严丝合缝也验证了代码的正确性。5. 常见问题与排查技巧5.1 经典翻车现场二分死循环二分写错最常见的问题就是死循环。初学者很容易写出这样的代码while (left right) { int mid (left right) / 2; if (check(mid)) { left mid; // 错可行时应该收右边界而不是推进左边界 } else { right mid - 1; } }如果可行时更新left mid当left和right相邻时mid会一直等于leftcheck(mid)一直为真left永远不变循环无法退出。我的经验是写二分之前先搞清楚你在找什么。找左边界就对应“可行时收右边界、不可行时推左边界”找右边界则反过来。如果实在记不住就把模板背下来再配合一两个样例做单调性推演基本不会错。5.2 段数判断的经典错误前面提过的cnt m错误值得在这里再强调一次。假设m 3但你在容量x下用 2 段就能装完所有元素这显然说明x是可行的。如果你写成cnt m就会把这种可行情况判成失败导致二分搜出来的答案偏大。更隐蔽的错误是在check里提前return false的条件写反。记住只有cnt m才需要提前终止因为再多一段都超过上限了。如果你写成cnt m就返回会把“恰好 m 段”这种合法情况也判为失败同样导致答案偏大。5.3 二分答案题型识别指南与贪心扩展LC410 只是二分答案家族里的一个代表。刷题多了你会发现凡是出现“最大值最小”“最小值最大”“在规定数量内完成”“在容量限制下装下”这类描述大概率都可以用“二分答案 验证”来解。同族题目包括LC875 爱吃香蕉的珂珂最小速度本质是“小时数不超过 h”的容量验证。LC1011 在 D 天内送达包裹的能力最小载重验证方式和 LC410 几乎一模一样。LC1552 两球之间的磁力最大化最小距离二分答案的反向操作。LC1482 制作 m 束花所需的最少天数同样是单调性验证。这些题的验证函数五花八门但骨架完全一致猜答案、写check、定边界。一旦你形成这个肌肉记忆见到类似题会非常省力。顺便提一下另一种贪心思路——跳跃游戏 IILC45。它跟二分答案无关但同样是贪心的经典应用在每一步都记录当前可达的最远位置当走到当前步的边界时步数加一同时把可跳范围更新为新的最远距离。这个“能走就多走走不动了才计数”的思维和 LC410 里“能装就装装不下才开新段”如出一辙。贪心的本质就是“局部最优推导全局最优”前提是问题要满足某种单调性或者无后效性。你可以把 LC410 和 LC45 放在一起对比着刷对贪心的理解会非常透彻。我再分享一个个人习惯做这类题时我会把二分模板和check函数分开写先单独测试check的正确性再组装整体逻辑。比如面对nums [1, 2, 3, 4, 5], m 2手动算一下check(8)为假、check(9)为真确认验证函数本身没问题再跑二分这样排错效率很高。如果你上来就整个写完再调试出了问题可能很难分清是二分边界错了还是check逻辑错了。按这个顺序排查绝大多数情况都能一次通过。