What is the main strategy to solve Magnetic Force Between Two Balls?

The core strategy is binary search over the valid minimum distances and using greedy placement to verify feasibility.

Why is sorting the positions necessary?

Sorting ensures you can check ball placements sequentially, which is essential for greedy feasibility checks and correct binary search results.

Can we directly try all distances between baskets?

Directly testing all distances is inefficient; binary search reduces the problem to O(n log(max_distance)) time, handling large inputs efficiently.

How does the pattern 'binary search over the valid answer space' apply here?

Instead of searching positions, you search the possible minimum forces and verify each with greedy placement, exactly matching this pattern.

What common mistakes should I avoid in this problem?

Do not skip sorting, incorrectly update the binary search range, or assume any arbitrary basket pairs determine the maximum force.

#1552

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

两球之间的磁力

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间最小磁力最大。已知两个球如果分别位于 x 和 …

数组二分查找排序

题目描述

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

示例 1：

输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2：

输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

提示：

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
所有 position 中的整数 互不相同 。
2 <= m <= position.length

lightbulb

解题思路

方法一：二分查找

我们注意到，任意两球间的最小磁力越大，能够放入的球的数量就越少，这存在着单调性。我们可以使用二分查找，找到最大的最小磁力，使得能够放入的球的数量不小于 $m$ 。

我们首先对篮子的位置进行排序，然后使用二分查找的方法，定义二分查找的左边界 $l = 1$ ，右边界 $r = \textit{position}[n - 1]$ ，其中 $n$ 为篮子的数量。在每次二分查找的过程中，我们计算取中值 $m = (l + r + 1) / 2$ ，然后判断是否存在一种放置球的方法，使得能够放入的球的数量不小于 $m$ 。

问题转换为判断一个给定的最小磁力 $f$ 是否能够放入 $m$ 个球。我们可以从左到右遍历篮子的位置，如果上一个球的位置与当前篮子的位置的距离大于等于 $f$ ，则说明可以在当前篮子放置一个球。最后判断放置的球的数量是否不小于 $m$ 即可。

时间复杂度 $O(n \times \log n + n \times \log M)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 和 $M$ 分别为篮子的数量和篮子的位置的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(f: int) -> bool:
            prev = -inf
            cnt = 0
            for curr in position:
                if curr - prev >= f:
                    prev = curr
                    cnt += 1
            return cnt < m

        position.sort()
        l, r = 1, position[-1]
        return bisect_left(range(l, r + 1), True, key=check)

speed

复杂度分析

指标	值
时间	O(n \log \frac{n * k}{m})
空间	O( \log n )

psychology

面试官常问的追问

外企场景

question_mark
Sorting positions before attempting placements is essential to make greedy checks feasible.
question_mark
Binary search over distances rather than positions is a critical insight for this problem pattern.
question_mark
Greedy placement confirms feasibility and drives the adjustment of the binary search range.

warning

常见陷阱

外企场景

error
Failing to sort positions before placement leads to incorrect feasibility checks.
error
Assuming the maximum force occurs between consecutive baskets rather than using binary search over the answer space.
error
Incorrectly updating the binary search range by not considering that smaller distances are always feasible once a larger distance works.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of maximizing the minimum force, minimize the maximum force between balls in baskets.
arrow_right_alt
Allow balls to be placed in non-integer positions and compute the optimal minimum distance.
arrow_right_alt
Change the force function from |x - y| to a custom metric and use the same binary search pattern.

help

常见问题

外企场景

继续练习

#1508 子数组和排序后的区间和 #1498 满足条件的子序列数目 #1608 特殊数组的特征值