题目描述
思路解析动画文字版
记住「间距越小越好放」这个单调性,下面在间距区间 [1, 6] 上二分,每个候选 d 都贪心放一遍球。
第一次二分:还没确定的间距范围是 [1, 6]。取上中点 d = 4(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 4 能放下几个。
贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 4 远就再放一个。
看位置 2:它离上一个放球点 1 只有 1,不到 4,太近,跳过不放。
看位置 3:它离上一个放球点 1 只有 2,不到 4,太近,跳过不放。
看位置 4:它离上一个放球点 1 只有 3,不到 4,太近,跳过不放。
看位置 7:它离上一个放球点 1 有 6,6≥4,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
这一趟用间距 4 只放下 2 个球,不够 3 个,说明 4 太大放不下;把右界压到 3、往小找。
第二次二分:还没确定的间距范围是 [1, 3]。取上中点 d = 2(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 2 能放下几个。
贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 2 远就再放一个。
看位置 2:它离上一个放球点 1 只有 1,不到 2,太近,跳过不放。
看位置 3:它离上一个放球点 1 有 2,2≥2,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
看位置 4:它离上一个放球点 3 只有 1,不到 2,太近,跳过不放。
看位置 7:它离上一个放球点 3 有 4,4≥2,够远,放下第 3 个球(绿色),这里成为新的上一个放球点。
这一趟用间距 2 放下了 3 个球,够 3 个,说明 2 可行;还想更大,所以把左界提到 2、继续往大试。
第三次二分:还没确定的间距范围是 [2, 3]。取上中点 d = 3(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 3 能放下几个。
贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 3 远就再放一个。
看位置 2:它离上一个放球点 1 只有 1,不到 3,太近,跳过不放。
看位置 3:它离上一个放球点 1 只有 2,不到 3,太近,跳过不放。
看位置 4:它离上一个放球点 1 有 3,3≥3,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
看位置 7:它离上一个放球点 4 有 3,3≥3,够远,放下第 3 个球(绿色),这里成为新的上一个放球点。
这一趟用间距 3 放下了 3 个球,够 3 个,说明 3 可行;还想更大,所以把左界提到 3、继续往大试。
间距区间收成一个点:3。用它能放下 3 个球、正好够 3 个,而再大一格就放不下了,所以最小间距最大就是 3(球放在位置 1、4、7)。回头看,我们没去枚举所有放法,只靠单调性二分了 3 次、每次贪心校验一遍就锁定了答案。
边界:m=2 取两端跨度;m=篮子数时被相邻最小间距卡住;务必先排序。
二分答案三件套:有序取值范围 + 单调判定 + O(n) 贪心验证;最大化用上中点。
参考代码
from typing import Listclass Solution: def maxDistance(self, position: List[int], m: int) -> int: position.sort() def ok(d): count, last = 1, position[0] for x in position[1:]: if x - last >= d: count += 1 last = x return count >= m l, r = 1, position[-1] - position[0] while l < r: mid = (l + r + 1) // 2 if ok(mid): l = mid else: r = mid - 1 return l复杂度
- 时间：O(n log n + n log(max−min))，先排序 position 是 O(n log n);再在间距区间 [1, max−min] 上二分 O(log(max−min)) 次、每次 O(n) 贪心校验,这部分 O(n log(max−min))
- 空间：O(1) 额外，贪心只用 count、last 几个变量,额外空间 O(1);若把排序也计入,C++ 和 Java 约 O(log n) 递归栈,Python 的 list.sort 最坏要 O(n) 辅助空间
易错点
面试追问把动画讲成自己的话
追问这属于哪类套路?
追问怎么确定二分方向和取中点?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每个小孩最多分到的糖果数
LeetCode 2226 · 中等 · 沿着 二分答案套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题