两球之间的磁力 图解题解
这道题到底在问什么
- 输入
- position=[1,2,3,4,7], m=3
- 输出
- 3(放在 1、4、7)
- 输入
- position=[1,2,4,8,9], m=3
- 输出
- 3
先想最直接的笨办法
第一次二分:还没确定的间距范围是 [1, 6]。取上中点 d = 4(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 4 能放下几个。（动画第 4 步）
最优解：一步一步想明白
- 3记住「间距越小越好放」这个单调性,下面在间距区间 [1, 6] 上二分,每个候选 d 都贪心放一遍球。
- 4第一次二分:还没确定的间距范围是 [1, 6]。取上中点 d = 4(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 4 能放下几个。
- 5贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 4 远就再放一个。
- 6看位置 2:它离上一个放球点 1 只有 1,不到 4,太近,跳过不放。
- 7看位置 3:它离上一个放球点 1 只有 2,不到 4,太近,跳过不放。
- 8看位置 4:它离上一个放球点 1 只有 3,不到 4,太近,跳过不放。
- 9看位置 7:它离上一个放球点 1 有 6,6≥4,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
- 10这一趟用间距 4 只放下 2 个球,不够 3 个,说明 4 太大放不下;把右界压到 3、往小找。
- 11第二次二分:还没确定的间距范围是 [1, 3]。取上中点 d = 2(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 2 能放下几个。
- 12贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 2 远就再放一个。
- 13看位置 2:它离上一个放球点 1 只有 1,不到 2,太近,跳过不放。
- 14看位置 3:它离上一个放球点 1 有 2,2≥2,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
- 15看位置 4:它离上一个放球点 3 只有 1,不到 2,太近,跳过不放。
- 16看位置 7:它离上一个放球点 3 有 4,4≥2,够远,放下第 3 个球(绿色),这里成为新的上一个放球点。
- 17这一趟用间距 2 放下了 3 个球,够 3 个,说明 2 可行;还想更大,所以把左界提到 2、继续往大试。
- 18第三次二分:还没确定的间距范围是 [2, 3]。取上中点 d = 3(取上中点是因为可行时要 l = d,不取上会死循环)。试试两球至少隔 3 能放下几个。
- 19贪心从最左开始:第 1 个球放在位置 1(绿色),它当作上一个放球点。往右看每个篮子,够 3 远就再放一个。
- 20看位置 2:它离上一个放球点 1 只有 1,不到 3,太近,跳过不放。
- 21看位置 3:它离上一个放球点 1 只有 2,不到 3,太近,跳过不放。
- 22看位置 4:它离上一个放球点 1 有 3,3≥3,够远,放下第 2 个球(绿色),这里成为新的上一个放球点。
- 23看位置 7:它离上一个放球点 4 有 3,3≥3,够远,放下第 3 个球(绿色),这里成为新的上一个放球点。
- 24这一趟用间距 3 放下了 3 个球,够 3 个,说明 3 可行;还想更大,所以把左界提到 3、继续往大试。
- 25间距区间收成一个点:3。用它能放下 3 个球、正好够 3 个,而再大一格就放不下了,所以最小间距最大就是 3(球放在位置 1、4、7)。回头看,我们没去枚举所有放法,只靠单调性二分了 3 次、每次贪心校验一遍就锁定了答案。
⚠️ 容易写错的地方
✗ 错：在数组下标上二分,或用下中点配 l = mid
✓ 对：在间距区间 [1, max−min] 上二分答案,取上中点 mid = (l + r + 1) // 2
二分的是答案(最小间距)本身、不是篮子下标;可行时 l = mid,用下中点会在 l、r 相邻时死循环
✗ 错：忘了先排序 position
✓ 对：先 sort 再贪心从左到右放
贪心「尽早放下一个」依赖位置有序,否则间距判断会错
✗ 错：贪心时纠结放哪个
✓ 对：从左到右,够远就立刻放
同样的间距门槛下,尽早放能给后面留最多空间,放得最多
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 lC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
auto ok = [&](int d) {
int count = 1, last = position[0];
for (int x : position) if (x - last >= d) { count++; last = x; }
return count >= m;
};
int l = 1, r = position.back() - position.front();
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (ok(mid)) l = mid; else r = mid - 1;
}
return l;
}
};Java
import java.util.*;
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int l = 1, r = position[position.length - 1] - position[0];
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (ok(position, m, mid)) l = mid;
else r = mid - 1;
}
return l;
}
private boolean ok(int[] position, int m, int d) {
int count = 1, last = position[0];
for (int x : position) if (x - last >= d) { count++; last = x; }
return count >= m;
}
}复杂度
时间
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) 辅助空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两球之间的磁力 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这属于哪类套路?+
「二分答案 + 贪心/判定」:答案落在一个有序取值范围里,且「某候选是否可行」随候选单调,就二分候选、用一个 O(n) 的判定函数验证。本题判定函数是贪心放球数 ≥ m。同类还有「使结果不超过阈值的最小除数」「在 D 天内送达包裹的最小运力」「分割数组的最大值最小」等。
怎么确定二分方向和取中点?+
本题要最大化最小间距,可行(放得下)时往大试 l = mid、不可行往小 r = mid − 1,所以用上中点 mid = (l + r + 1) // 2 防死循环;最后 l 收敛到最大可行间距。和「找最小值」那类(可行往小收 r = mid)正好镜像。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 两球之间的磁力 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。