题目描述
思路解析
一句话答案：LeetCode 1760 袋子里最少数目的球用二分答案：最大的那袋球数越大越好拆、可行性单调，就在 1 到 max(nums) 上二分这个最大值，用 (x-1)//m 累加分裂次数判定。时间 O(n·log C)、空间 O(1)。
拆袋子换更小的最大值，这题要返回哪个数
给你一排袋子，nums[i] 是第 i 个袋子的球数，还有上限 maxOperations。一次操作挑一个袋子、把球分成两个正整数堆（比如 5 拆成 1 和 4），最多拆这么多次。开销 = 所有袋子球数的最大值，要让它尽量小并返回。题面 nums=[2,4,8,2]、maxOperations=4 答案是 2：拆满 4 次能把最大值压到 2。
从 1 到最大袋逐个试开销，账算下来多亏
开销最小是 1（每袋只剩 1 个球），最大是 max(nums)（一次都不拆）。笨办法是从 1 到 max(nums) 逐个开销试，每试一个就逐袋算要拆几次、看超不超 maxOperations。可开销是值域（所有可能取值），nums 里的数能到 10⁹，挨个试要扫这么多档、每档还得过一遍 n 个袋子，跑不完。
上限越大越省操作，这条单调让答案可二分
开销 m 定得越大，每个袋子拆到不超过 m 需要的次数越少，总次数跟着往下走；m 越小则越多。开销越大操作只会越少、不回头，于是开销小到某处以下全都拆不完、以上全都够，答案就是第一个够的开销。这条单调分界一立住，就能二分开销逼近它。二分的是开销 m 这个答案值，不是 nums 下标，数组也不用排序。这种猜一个开销再验证行不行的思路，叫二分答案。
判定函数怎么写，(x-1)//m 里那个减 1 从哪来
先把「行不行」做成判定函数 check(m)：逐袋累加分裂次数，总和 ≤ maxOperations 就可行。单袋分裂次数是关键——把 x 个球拆到每袋不超过 m，至少要 ceil(x/m)（向上取整）个袋子；分裂从 1 个整袋起步、每拆一次多一个袋子，凑够就得拆 ceil(x/m)-1 次，减的这个 1 是起步那个整袋。恒等式 ceil(x/m)-1 正好等于 (x-1)//m。二分取中点 mid：可行就 hi 收到 mid（得留住候选），不可行就 lo 跳到 mid+1，撞上就是答案。
nums=[2,4,8,2]、上限 4 走一遍
起点 lo=1、hi=max(nums)=8。第一轮 mid=(1+8)//2=4，(x-1)//4：2→0，4→0，8→(8-1)//4=1，2→0，合计 1 ≤ 4 可行，hi 收到 4。第二轮 lo=1、hi=4，mid=2，(x-1)//2：0、(4-1)//2=1、(8-1)//2=3、0，合计 4 ≤ 4 可行，hi 收到 2。第三轮 lo=1、hi=2，mid=1，(x-1)//1：1、3、7、1，合计 12 > 4 不可行，lo 跳到 2。此时 lo=hi=2，返回 2。
可行时右界收到 mid，减 1 就把答案跳过去
这套 lo<hi、返回 lo 的写法里可行时必须 hi=mid：当前 mid 可能就是最小可行开销，写成 hi=mid-1 会把它甩出区间、返回错的值。另一个坑是把二分架在数组下标上，这题二分的是开销值，认错对象会整个跑偏。复杂度上，开销 1 到 C（C=max(nums)）二分约 log C 轮、每轮 check 扫 n 个袋子，时间 O(n·log C)、空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:开销 m 越大越好办,可行性单调,于是在 1 到 max(nums) 上二分 m。检查一个 m:每个袋子分裂 (x-1)//m 次,求和 ≤ maxOperations 则可行、收紧右界,否则抬高左界。二分的是开销值,不是下标。
总览 · 想压小最大的袋子：先看清画面。上面这排格子是 4 个袋子 2,4,8,2,开销就是里面最大的那个,现在是 8。我们最多拆 4 次,想把这个最大值压到尽量小。右边面板记三件事:开销的候选范围、当前正在检验的开销 m、已经用掉的分裂次数,现在都还没开始。思路不是硬拆,而是二分猜一个开销 m,再验证它办不办得到。
定范围 · 在 1 到 8 上二分开销：先框定答案的范围。开销最小能到 1,每袋只放 1 个球;最大不用超过 8,因为一次都不拆时最大袋就是 8。所以答案一定落在 1 到 8 这个闭区间里。接下来我们不逐个试,而是二分:取中点当候选开销 m,验证「能不能让每个袋子都不超过 m」。请记住,右边面板里动的是开销 m 的范围,不是数组下标,数组这排袋子始终不动。
第一轮 · 取中点 m = 4：开始第一轮二分。当前范围是 1 到 8,取中点,m 等于 1 加 8 整除 2 得 4。也就是先问:能不能拆到每个袋子都不超过 4 个球?下面逐个袋子算它要分裂几次,把次数累加起来,再和上限 4 比。
第一轮 · 检验袋子0(2个)：看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 4。至少需要 2 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
第一轮 · 检验袋子1(4个)：看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 4。至少需要 4 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
第一轮 · 检验袋子2(8个)：看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 4。至少需要 8 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 4,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
第一轮 · 检验袋子3(2个)：看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 4。至少需要 2 除以 4 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 4,算出来是 0 次。这个袋子本来就不超过 4,一次都不用拆。
第一轮 · m = 4 可行：四个袋子算完,分裂合计 1 次,不超过上限 4,说明开销压到 4 是办得到的。既然能到 4,那更大的开销就不用看了,把右界收到 4,范围变成 1 到 4。注意 4 本身可能就是答案,所以右界取 4 而不是 4 减 1,继续往更小里试。
第二轮 · 取中点 m = 2：第二轮二分。上一轮把范围收到了 [1, 4],取中点得到候选开销 m 等于 2。同样地,问一句:能不能让每个袋子都不超过 2 个球?逐袋算分裂次数、累加、再和上限 4 比。
第二轮 · 检验袋子0(2个)：看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 2。至少需要 2 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 2,算出来是 0 次。这个袋子本来就不超过 2,一次都不用拆。
第二轮 · 检验袋子1(4个)：看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 2。至少需要 4 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 2,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
第二轮 · 检验袋子2(8个)：看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 2。至少需要 8 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 2,算出来是 3 次。把它累加进已用分裂,现在合计 4 次。
第二轮 · 检验袋子3(2个)：看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 2。至少需要 2 除以 2 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 2,算出来是 0 次。这个袋子本来就不超过 2,一次都不用拆。
第二轮 · m = 2 可行：四个袋子算完,分裂合计 4 次,不超过上限 4,说明开销压到 2 是办得到的。既然能到 2,那更大的开销就不用看了,把右界收到 2,范围变成 1 到 2。注意 2 本身可能就是答案,所以右界取 2 而不是 2 减 1,继续往更小里试。
第三轮 · 取中点 m = 1：第三轮二分。上一轮把范围收到了 [1, 2],取中点得到候选开销 m 等于 1。同样地,问一句:能不能让每个袋子都不超过 1 个球?逐袋算分裂次数、累加、再和上限 4 比。
第三轮 · 检验袋子0(2个)：看第 0 个袋子,里面有 2 个球,要拆到每袋不超过 1。至少需要 2 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 1,算出来是 1 次。把它累加进已用分裂,现在合计 1 次。
第三轮 · 检验袋子1(4个)：看第 1 个袋子,里面有 4 个球,要拆到每袋不超过 1。至少需要 4 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 4 减 1 再整除 1,算出来是 3 次。把它累加进已用分裂,现在合计 4 次。
第三轮 · 检验袋子2(8个)：看第 2 个袋子,里面有 8 个球,要拆到每袋不超过 1。至少需要 8 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 8 减 1 再整除 1,算出来是 7 次。把它累加进已用分裂,现在合计 11 次。
第三轮 · 检验袋子3(2个)：看第 3 个袋子,里面有 2 个球,要拆到每袋不超过 1。至少需要 2 除以 1 向上取整个袋子,从一个袋子拆成这么多个,分裂次数就是它减 1,写成整除是 2 减 1 再整除 1,算出来是 1 次。把它累加进已用分裂,现在合计 12 次。
第三轮 · m = 1 不可行：四个袋子算完,分裂合计 12 次,超过了上限 4,说明开销压到 1 太狠、拆不过来。那 1 以及更小的都不行,把左界抬到 2,范围变成 2 到 2。左右界撞到一起了,二分到此收束。
收束 · 左右界重合于 2：二分收束了。左界和右界都停在 2,说明 2 是能办到的最小开销:它可行,而比它小的 1 已经验证过办不到。把开销压到 2 的具体拆法是,那个 8 拆成 4 和 4、再各自拆成两个 2,4 也拆成两个 2,恰好用满 4 次分裂,最后全场每袋都不超过 2。
完成 · 最小开销 = 2：收个尾。整道题的巧劲在于把「怎么拆」这个难题,翻译成「开销能不能压到 m」这个好答的判断题,再靠单调性二分开销。nums = 2,4,8,2、maxOperations = 4,我们只检验了 4、2、1 三个候选开销,就锁定最小开销是 2。二分让候选个数从线性变成对数级,可行性检查每次线性扫一遍袋子,又快又稳。
边界:[9] 拆 1 次最小开销 5(分成 4 和 5);[9] 拆 2 次开销 3(拆成 3,3,3);[1] 无论多少次都是 1(拆不动)。都能用 (x-1)//m 的可行性检查验证。
面试重点:开销越大越可行,可行性单调所以能二分;单袋分裂次数 (x-1)//m 来自 ceil(x/m) 减 1;难点是自己设计可行性判定,把求最优翻译成判定「能不能达到 m」,范围取 1 到 max(nums)、可行时右界取 mid。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def minimumSize(self, nums: List[int], maxOperations: int) -> int: def check(mx: int) -> bool: return sum((x - 1) // mx for x in nums) <= maxOperations return bisect_left(range(1, max(nums) + 1), True, key=check) + 1复杂度
- 时间：O(n log C)，n 是袋子个数,C 是最大的袋子球数 max(nums)。二分在开销范围 1 到 C 上进行,最多 log C 轮;每一轮做一次可行性检查,要扫一遍全部 n 个袋子累加分裂次数,是 O(n)。两者相乘就是 O(n log C)。演示里 n 等于 4、C 等于 8,只检验了 3 个候选开销就收敛
- 空间：O(1)，按峰值算。除了输入数组,只用了 lo、hi、mid 和一个累加分裂次数的变量,都是常数个标量,不随规模增长。Python 里的 range 是惰性对象、不真的展开成数组,bisect 也只用常数额外空间。全程没有开新数组,所以额外空间是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么开销可以拿来二分?单调性到底体现在哪?
追问单个袋子的分裂次数为什么正好是 (x-1)//m?
追问和普通的「在有序数组里二分找目标」比,这题难在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下标对中的最大距离
LeetCode 1855 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题