企业官网建设流程全解析

刷题的朋友对 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 = 0，check(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(vector<int>& 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 的一段拆成 1+2 两段，每段的和只会更小，依然小于等于 x。拆分的操作不会破坏“每段和不超过 x”这个约束。

所以正确的判断条件是cnt <= m，而不是cnt == m。这个细节直接决定了正确性：写成==会漏掉大量可行答案，导致二分最终结果偏大。

3.3 与二分模板配合的细节

有了check，主函数只需要在这个单调区间上做标准二分即可：

int splitArray(vector<int>& 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(vector<int>& 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(vector<int>& 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 vector<int>&。

对比一下暴力枚举和动态规划方案：

所以这道题的最优解，不是更复杂的状态转移，而是这种“猜答案 + 验证”的思辨方式，这也是二分答案这类题型的魅力所在。

4.3 用示例手动推演一遍

拿题目的经典样例nums = [7, 2, 5, 10, 8], m = 2来手工模拟：

初始：left = max(nums) = 10，right = sum(nums) = 32。

第一轮，mid = (10 + 32) / 2 = 21。check(21)：扫描数组，7+2+5=14 没超，再加 10 变成 24 超了，开新段，cur=10，加 8 变成 18，没超。最终用了 2 段，cnt <= 2成立，所以答案不高于 21，right = 21。

第二轮，mid = (10 + 21) / 2 = 15。check(15)：7+2+5=14 没超，加 10 超了，开段cur=10，加 8 变成 18 又超了，再开段cur=8。最终用了 3 段，cnt > 2失败，所以答案必须大于 15，left = 16。

第三轮，mid = (16 + 21) / 2 = 18。check(18)：7+2+5=14 没超，加 10 变成 24 超了，开段cur=10，加 8 变成 18，没超。最终用了 2 段，可行，right = 18。

第四轮，mid = (16 + 18) / 2 = 17。check(17)：7+2+5=14 没超，加 10 超了，开段cur=10，加 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会一直等于left，check(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、定边界。一旦你形成这个肌肉记忆，见到类似题会非常省力。

顺便提一下另一种贪心思路——跳跃游戏 II（LC45）。它跟二分答案无关，但同样是贪心的经典应用：在每一步都记录当前可达的最远位置，当走到当前步的边界时，步数加一，同时把可跳范围更新为新的最远距离。这个“能走就多走，走不动了才计数”的思维，和 LC410 里“能装就装，装不下才开新段”如出一辙。贪心的本质就是“局部最优推导全局最优”，前提是问题要满足某种单调性或者无后效性。你可以把 LC410 和 LC45 放在一起对比着刷，对贪心的理解会非常透彻。

我再分享一个个人习惯：做这类题时，我会把二分模板和check函数分开写，先单独测试check的正确性，再组装整体逻辑。比如面对nums = [1, 2, 3, 4, 5], m = 2，手动算一下check(8)为假、check(9)为真，确认验证函数本身没问题，再跑二分，这样排错效率很高。如果你上来就整个写完再调试，出了问题可能很难分清是二分边界错了还是check逻辑错了。按这个顺序排查，绝大多数情况都能一次通过。