题目描述
思路解析动画文字版
记住「除数越大总和越小」这个单调性,下面在除数轴 [1, 9] 上二分。
这是除数候选轴 [1, 9]:除数太小总和会超阈值,除数太大虽然达标但不是最小,真正的最小答案落在某个临界点。逐个试要查 9 次,二分只要几次。l 指 1、r 指 9,开始二分。
第一次二分:还没排除的除数范围是 [1, 9](灰格已排除)。取中点除数 m = 5,算一下用它当除数时的总和。
把 1 除以除数 5 向上取整,得 1;累计总和到 1。
把 2 除以除数 5 向上取整,得 1;累计总和到 2。
把 5 除以除数 5 向上取整,得 1;累计总和到 3。
把 9 除以除数 5 向上取整,得 2;累计总和到 5。这就是 f(5) 的全部。
总和 f(5) = 5,没超过阈值 6,说明除数 5 已经够大;更小的除数可能也行,所以把右界收到 5、继续往小找。
第二次二分:还没排除的除数范围是 [1, 5](灰格已排除)。取中点除数 m = 3,算一下用它当除数时的总和。
把 1 除以除数 3 向上取整,得 1;累计总和到 1。
把 2 除以除数 3 向上取整,得 1;累计总和到 2。
把 5 除以除数 3 向上取整,得 2;累计总和到 4。
把 9 除以除数 3 向上取整,得 3;累计总和到 7。这就是 f(3) 的全部。
总和 f(3) = 7,超过了阈值 6,说明除数 3 太小、总和太大;答案一定更大,把左界推到 4。
第三次二分:还没排除的除数范围是 [4, 5](灰格已排除)。取中点除数 m = 4,算一下用它当除数时的总和。
把 1 除以除数 4 向上取整,得 1;累计总和到 1。
把 2 除以除数 4 向上取整,得 1;累计总和到 2。
把 5 除以除数 4 向上取整,得 2;累计总和到 4。
把 9 除以除数 4 向上取整,得 3;累计总和到 7。这就是 f(4) 的全部。
总和 f(4) = 7,超过了阈值 6,说明除数 4 太小、总和太大;答案一定更大,把左界推到 5。
区间收成一个点:除数 5。它的总和 5 不超过阈值 6,而再小一格就会超标,所以它就是最小除数,答案 5。回头看,我们没去逐个试 1 到 9,只靠单调性二分了 3 次就锁定了。
边界:除数到 max 时总和 = n;阈值越紧、需要的除数越大。
二分答案三件套:有序取值范围 + 单调判定函数 + O(n) 验证。
参考代码
from typing import Listclass Solution: def smallestDivisor(self, nums: List[int], threshold: int) -> int: l, r = 1, max(nums) while l < r: m = (l + r) // 2 if sum((x + m - 1) // m for x in nums) <= threshold: r = m else: l = m + 1 return l复杂度
- 时间：O(n log(maxNum))，除数区间 [1, max(nums)] 上二分 O(log maxNum) 次,每次 O(n) 求一遍 f(m)
- 空间：O(1)，只用 l、r、m、sum 几个变量
易错点
面试追问把动画讲成自己的话
追问这属于哪类套路?
追问判定函数怎么定方向?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
制作 m 束花所需的最少天数
LeetCode 1482 · 中等 · 沿着 二分答案套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题