使结果不超过阈值的最小除数 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,5,9], threshold=6
- 输出
- 5
- 输入
- nums=[44,22,33,11,1], threshold=5
- 输出
- 44
最优解：一步一步想明白
- 3记住「除数越大总和越小」这个单调性,下面在除数轴 [1, 9] 上二分。
- 4这是除数候选轴 [1, 9]:除数太小总和会超阈值,除数太大虽然达标但不是最小,真正的最小答案落在某个临界点。逐个试要查 9 次,二分只要几次。l 指 1、r 指 9,开始二分。
- 5第一次二分:还没排除的除数范围是 [1, 9](灰格已排除)。取中点除数 m = 5,算一下用它当除数时的总和。
- 6把 1 除以除数 5 向上取整,得 1;累计总和到 1。
- 7把 2 除以除数 5 向上取整,得 1;累计总和到 2。
- 8把 5 除以除数 5 向上取整,得 1;累计总和到 3。
- 9把 9 除以除数 5 向上取整,得 2;累计总和到 5。这就是 f(5) 的全部。
- 10总和 f(5) = 5,没超过阈值 6,说明除数 5 已经够大;更小的除数可能也行,所以把右界收到 5、继续往小找。
- 11第二次二分:还没排除的除数范围是 [1, 5](灰格已排除)。取中点除数 m = 3,算一下用它当除数时的总和。
- 12把 1 除以除数 3 向上取整,得 1;累计总和到 1。
- 13把 2 除以除数 3 向上取整,得 1;累计总和到 2。
- 14把 5 除以除数 3 向上取整,得 2;累计总和到 4。
- 15把 9 除以除数 3 向上取整,得 3;累计总和到 7。这就是 f(3) 的全部。
- 16总和 f(3) = 7,超过了阈值 6,说明除数 3 太小、总和太大;答案一定更大,把左界推到 4。
- 17第三次二分:还没排除的除数范围是 [4, 5](灰格已排除)。取中点除数 m = 4,算一下用它当除数时的总和。
- 18把 1 除以除数 4 向上取整,得 1;累计总和到 1。
- 19把 2 除以除数 4 向上取整,得 1;累计总和到 2。
- 20把 5 除以除数 4 向上取整,得 2;累计总和到 4。
- 21把 9 除以除数 4 向上取整,得 3;累计总和到 7。这就是 f(4) 的全部。
- 22总和 f(4) = 7,超过了阈值 6,说明除数 4 太小、总和太大;答案一定更大,把左界推到 5。
- 23区间收成一个点:除数 5。它的总和 5 不超过阈值 6,而再小一格就会超标,所以它就是最小除数,答案 5。回头看,我们没去逐个试 1 到 9,只靠单调性二分了 3 次就锁定了。
⚠️ 容易写错的地方
✗ 错：在数组下标上二分
✓ 对：在除数取值区间 [1, max(nums)] 上二分答案
二分的对象是答案本身,不是数组位置
✗ 错：靠浮点除法算 ceil
✓ 对：用整数 (x + m − 1) // m 求向上取整
浮点有精度风险,整数写法稳
✗ 错：f(m) 求和用 int 可能溢出
✓ 对：求和用 long / long long
累加值大时会超 int
✗ 错：命中后还往右找
✓ 对：f(m) ≤ threshold 时 r = m 继续往左
要的是最小除数
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 lC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int l = 1, r = *max_element(nums.begin(), nums.end());
while (l < r) {
int m = l + (r - l) / 2;
long long sum = 0;
for (int x : nums) sum += (x + m - 1) / m;
if (sum <= threshold) r = m;
else l = m + 1;
}
return l;
}
};Java
import java.util.*;
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int l = 1, r = 1;
for (int x : nums) r = Math.max(r, x);
while (l < r) {
int m = l + (r - l) / 2;
long sum = 0;
for (int x : nums) sum += (x + m - 1) / m;
if (sum <= 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 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使结果不超过阈值的最小除数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这属于哪类套路?+
「二分答案」:答案在一个有序的取值范围里、且「某个候选是否可行」随候选单调变化,就能二分候选、用一个 O(n) 的判定函数验证。本题判定函数是 f(m) ≤ threshold。同类还有「分割数组的最大值最小」「在 D 天内送达包裹的最小运力」等。
判定函数怎么定方向?+
看单调性:除数变大 f 变小。我们要最小的、能让 f ≤ threshold 的除数,所以可行(f ≤ threshold)时往左收 r = m、不可行时往右 l = m+1,最后 l 收敛到最小可行除数。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使结果不超过阈值的最小除数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。