LeetCode 1552 - 两球之间的磁力

题目

给定一个数组 position 表示球的位置，以及整数 m 表示要放的球数。把 m 个球放入这些位置，使任意两球间的最小磁力（距离）最大。返回这个最大值。

解题思路

先对位置排序。
对“最小间距”进行二分搜索：假设最小间距为 d，检查能否放下 m 个球。
检查方式：从最左位置开始贪心放球，尽量保持相邻球间距 ≥ d，统计能放下的球数。

如果能放下 m 个球，说明 d 可行，尝试更大；否则缩小。

代码实现（Python）

from typing import List


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

        def can_place(dist: int) -> bool:
            count = 1
            last = position[0]
            for x in position[1:]:
                if x - last >= dist:
                    count += 1
                    last = x
                    if count >= m:
                        return True
            return count >= m

        left, right = 1, position[-1] - position[0]
        while left < right:
            mid = (left + right + 1) // 2
            if can_place(mid):
                left = mid
            else:
                right = mid - 1
        return left