---

1552. 两球之间的磁力

• 标签：数组、二分查找、排序
• 难度：中等

题目链接

• 1552. 两球之间的磁力 - 力扣

题目大意

描述：给定一个数组 $position$，表示 $n$ 个篮子的位置。有 $m$ 个球需要放入篮子中，每个篮子最多放一个球。

磁力定义为任意两个球之间的最小距离。目标是通过合理安排球的位置，使得最小磁力最大。

要求：返回最大化的最小磁力。

说明：

• $2 \le position.length \le 10^5$。
• $1 \le position[i] \le 10^9$。
• $2 \le m \le position.length$。

示例：

• 示例 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 的篮子时最小磁力最大。

解题思路

思路 1：二分答案 + 贪心验证

1. 核心思想

最小距离的最大化，是典型的二分答案问题。

答案范围：最小可能距离 $1$（两个球紧挨），最大可能距离 $\max(position) - \min(position)$（两个球放两端）。

验证函数 $check(dist)$：能否放置 $m$ 个球，使得任意两球间距 $\ge dist$。

贪心放置：对 $position$ 排序后，从第一个位置开始放球，每次选距离上一次放置 $\ge dist$ 的最左位置。

2. 具体步骤

第 1 步：对 $position$ 排序。

第 2 步：二分左边界 $l = 1$，右边界 $r = position[-1] - position[0]$。

第 3 步：当 $l < r$ 时：

• $mid = \lceil (l + r + 1) / 2 \rceil$。
• 如果 $check(mid)$ 为 True（可以放置），$l = mid$。
• 否则 $r = mid - 1$。

第 4 步：返回 $l$。

3. check 函数的贪心证明

排序后，从第一个篮子放第一个球，然后尽量选择离上一个球最远但至少 $dist$ 的位置。这种贪心策略能最大化剩余空间，因此如果这种策略放不下 $m$ 个球，其他策略也放不下。

4. 举例说明

以 $position = [1, 2, 3, 4, 7], m = 3$ 为例：

排序后 $[1, 2, 3, 4, 7]$。

二分过程：

• $l=1, r=6$，$mid=3$。
  • $check(3)$：位置 $1$ 放第 $1$ 个球，下一位置 $\ge 4$ 选 $4$ 放第 $2$ 个球，下一位置 $\ge 7$ 选 $7$ 放第 $3$ 个球。$\checkmark$，$l=3$。
• $l=3, r=6$，$mid=5$。
  • $check(5)$：$1 \to 7$（$1$ 到 $7$ 距离 $6 \ge 5$），但只能放 $2$ 个球。$\times$，$r=4$。
• $l=3, r=4$，$mid=4$。
  • $check(4)$：$1 \to 7$，只能放 $2$ 个球。$\times$，$r=3$。
• 返回 $l=3$。

最大最小磁力为 $3$。

思路 1：代码

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        n = len(position)

        def check(dist):
            count = 1
            last = position[0]
            for i in range(1, n):
                if position[i] - last >= dist:
                    count += 1
                    last = position[i]
                    if count >= m:
                        return True
            return False

        l, r = 1, position[-1] - position[0]
        while l < r:
            mid = (l + r + 1) // 2
            if check(mid):
                l = mid
            else:
                r = mid - 1

        return l

思路 1：复杂度分析

• 时间复杂度：$O(n \log n + n \log D)$，排序 $O(n \log n)$，二分 $\log D$ 次（$D$ 为最大值与最小值之差），每次验证 $O(n)$。
• 空间复杂度：$O(1)$。