二分答案（Binary Search on Answer）——LeetCode 875 Koko 吃香蕉 + 410 分割数组最大值，把“单调性判定/上界二分“一次讲透

摘要很多人学二分只停在在有序数组里找一个值但面试和真实工程里更高频的其实是二分答案——不在数组里找数而是在一个连续可行域上二分地逼近那个刚好可行的最优解。本文用 LeetCode 875Koko 吃香蕉和 410分割数组最大值这一对经典题把这套套路拆成可迁移的三步写判定函数、确认单调性、做 lower-bound 二分。所有代码本地 Python 跑通把真实样例输出和二分收敛过程一并写进来。关键词二分答案、Binary Search on Answer、LeetCode 875、LeetCode 410、单调性、上界二分、lower-boundTOC一、为什么二分答案是另一种二分8 月 20 日我们写过 DSA 第 12 篇《二分查找精讲——704 34》解决的是在有序数组里找某个 target 的下标。那种二分的搜索空间是数组下标判定条件是nums[mid] target。但有一类题答案不是数组里现成的元素而是某个我们可以自由枚举/逼近的数值——比如最小吃香蕉速度 k最大的段和最小能压到多少船最小载重。这类题的搜索空间是一个数值可行域一段连续整数我们要找的不是等于谁而是刚好可行的那个临界值。这就是二分答案Binary Search on Answer它和普通二分的区别一张图就能说清核心心法当你发现直接求最优解很难但给定一个候选答案 x判断它行不行却很容易并且这个行不行随 x 单调变化时就应该二分答案。二、套路三步走把二分答案抽象成固定三步以后遇到同类题照着套几个最容易翻车的点先记下来上下界怎么定下界是理论上最小可能值上界是理论上一定可行的最大/最松值。定错了二分直接错。单调性方向先想清楚x 变大P(x) 是越来越容易成立还是越来越难决定二分里lomid1还是himid-1。收敛到哪个值lohimid(lohi)//2这套 lower-bound 写法最终lohi就是第一个让 P 成立的最小值。三、LeetCode 875Koko 吃香蕉3.1 题意与建模有n堆香蕉piles[i]Koko 每小时选一堆吃一小时内最多吃k根如果这堆不足k根吃完这堆这一小时就结束。要求h小时内吃完所有堆求最小的k[S1]。按套路走判定函数 P(k)给定吃速k吃完所有堆需要多少小时每堆耗时ceil(pile / k)求和看是否 h。单调性k越大总耗时越少。所以能否在 h 小时吃完随k单调不减地成立——k 小了不行k 大了都行。可行域下界lo1至少每小时吃一根上界himax(piles)一小时吃完最大那堆显然可行。3.2 代码def min_eating_speed(piles, h): def can_finish(k): hours 0 for p in piles: hours (p k - 1) // k # ceil(p / k)整数写法避免浮点 return hours h lo, hi 1, max(piles) while lo hi: mid (lo hi) // 2 if can_finish(mid): # mid 可行 - 答案 mid试更小 hi mid else: # mid 吃不完 - 必须更大 lo mid 1 return lo注意(p k - 1) // k是整数版向上取整比math.ceil(p/k)更稳避免浮点误差。3.3 本地实测输出我在本地跑了 4 组样例含官方 3 组 一组超大数边界全部 PASS LeetCode 875. Koko Eating Bananas piles[3, 6, 7, 11], h8 - k4 (expect 4) [PASS] piles[30, 11, 23, 4, 20], h5 - k30 (expect 30) [PASS] piles[30, 11, 23, 4, 20], h6 - k23 (expect 23) [PASS] piles[1, 1, 1, 1000000000], h5 - k500000000 (expect 500000000) [PASS]最后一组是边界4 堆里有一堆是 10 亿根h5比堆数多 1 小时。答案5e8——大堆要分两小时吃完剩下三小堆各一小时正好 5 小时。这个用例专门用来验证二分在lo很紧、上界极大时不会溢出或收敛错。四、LeetCode 410分割数组的最大值4.1 题意与建模把一个非负数组nums切成m段连续子数组要让各段和的最大值尽可能小求这个最小的最大值 [S2]。这题比 875 绕一层不是直接求切法而是最小化最大段和。按套路判定函数 P(limit)给定一个每段和不许超过 limit的上限贪心扫描——能塞进当前段就塞塞不下就开新段。统计最少需要几段。单调性limit越大需要的段数越少。所以能否用m段装下随limit单调不减地成立。可行域下界lomax(nums)每段至少装下一个元素否则有元素永远装不下上界hisum(nums)不切整段装下。4.2 代码def split_array(nums, m): def min_groups(limit): groups, cur 1, 0 for x in nums: if cur x limit: groups 1 cur x else: cur x return groups lo, hi max(nums), sum(nums) while lo hi: mid (lo hi) // 2 if min_groups(mid) m: # mid 可行 - 试更小上界 hi mid else: lo mid 1 return lo这里有个值得讲透的点下界为什么必须是max(nums)而不是 0因为若limit小于最大元素那个元素无论怎么切都装不进任何一段判定函数直接失效。二分答案的可行域下界必须是哪怕最坏情况下也能成立的最小值这是和 875 不同的细节。4.3 本地实测输出 LeetCode 410. Split Array Largest Sum nums[7, 2, 5, 10, 8], m2 - max_sub_sum18 (expect 18) [PASS] nums[1, 2, 3, 4, 5], m2 - max_sub_sum9 (expect 9) [PASS] nums[1, 4, 4], m3 - max_sub_sum4 (expect 4) [PASS] nums[10, 20, 30, 40], m2 - max_sub_sum60 (expect 60) [PASS]4.4 二分到底是怎么一步步收敛的光看答案不够我把[7,2,5,10,8], m2这一例的二分过程打印出来你能直接看到 lower-bound 二分一收一放的节奏step0: lo10 hi32 mid21 - 需2段,可行,收紧上界 step1: lo10 hi21 mid15 - 需3段,不可行,抬低下界 step2: lo16 hi21 mid18 - 需2段,可行,收紧上界 step3: lo16 hi18 mid17 - 需3段,不可行,抬低下界 收敛答案 18mid21可行说明答案不超过 21于是hi21mid15要 3 段超过 m2说明答案必须 15于是lo16如此反复区间从[10,32]每次砍一半4 次就收敛到 18。这正是为什么复杂度是O(n log R)——log R次判定每次O(n)扫描。五、两道题放一起看套路的可迁移性维度875 Koko 吃香蕉410 分割数组我们在二分什么吃速 k段和上限 limit判定函数总耗时 h?所需段数 m?单调性方向k↑ 耗时↓可行门槛左移limit↑ 段数↓可行门槛左移下界 lo1max(nums)上界 himax(piles)sum(nums)二分收尾最小可行 k最小可行 limit把这张表记住等于把二分答案这个套路的骨架抽出来了。后续 1011D 天送包裹、1283使和小于阈值的最小除数、2439最小化数组最大值、875 的孪生题 2226装最多香蕉都是同一套判定函数换皮。六、面试与工程里的两个提醒提醒一先证明单调再上二分。二分答案不是万能的——如果行不行不随候选单调二分就会漏掉答案。写代码前先在脑子里或草稿上画一下候选 x 从最小到最大可行性是不是单调翻转一次翻多次就不能二分。提醒二判定函数要写得 O(n) 甚至更优。因为它会被调用log R次。875/410 的判定都是 O(n)所以总复杂度 O(n log R)如果你把判定写成 O(n²)整道题就退化成 O(n² log R)可能超时。七、总结二分答案的本质是把求最优这个难问题降维成判可行这个易问题再用二分把难问题的答案在可行域上搜出来。三步写判定函数、确认单调、lower-bound 二分找临界值。875 教你上下界从哪来410 教你贪心判定 紧下界。两道题跑完这套套路就不再是背模板而是你能在新题上现推的思维方式。参考资料LeetCode 875. Koko Eating Bananas 官方题面与约束一级官方2026 核对LeetCode 410. Split Array Largest Sum 官方题面与约束一级官方2026 核对本地脚本binary_search_on_answer.py实测输出2026-09-13Python 3.12全部样例 PASS