题目描述
思路解析动画文字版
记牢:开销 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题