两球之间的磁力

难度: Medium

在代号为 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

Submission

运行时间: 216 ms

内存: 28.7 MB

# class Solution:
#     def maxDistance(self, position: List[int], m: int) -> int:
#         position.sort()
#         def check(x: int) -> bool:
#             cnt = i = 1
#             pre = 0
#             while i < len(position):
#                 if position[i] - position[pre] >= x:
#                     cnt += 1
#                     pre = i
#                 i += 1
#             return cnt >= m
            

#         left, right = 1, position[-1] - position[0] // (m - 1)
#         while left <= right:
#             mid = (left + right) >> 1
#             # 检查mid能够作为任意两球间的最小磁力
#             if check(mid):
#                 left = mid + 1
#             else:
#                 right = mid - 1
#         return left - 1
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(mag):
            end = position[0]
            ball = 0
            for x in position:
                if x >= end:
                    ball += 1
                    end = x + mag
            return ball >= m

        position.sort()
        left = 1
        # 右边界优化
        right = (position[-1] - position[0]) // (m - 1)
        while right >= left:
            mid = left + right >> 1
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return left - 1

Explain

题解采用了二分查找的方法来确定最大的最小磁力。首先对位置数组进行排序，然后定义一个二分查找的范围，左边界为1（最小可能的磁力），右边界为(position[-1] - position[0]) // (m - 1)（当球均匀分布时的最小间距）。在二分查找过程中，使用一个辅助函数check来判断当前磁力值是否可行。该函数通过尝试放置球，看是否可以在保持至少当前磁力的前提下放下所有的球。如果可以放下，说明当前磁力可能偏小，增大左边界；否则减小右边界。最终left指向第一个不满足条件的磁力值，因此结果为left-1。

时间复杂度: O(n log(maxDistance))

空间复杂度: O(1)

# 解题代码添加了注释

# 定义解题类

class Solution:
    # 主函数
    def maxDistance(self, position: List[int], m: int) -> int:
        # 检查给定的磁力是否可以使得放置m个球
        def check(mag):
            # 初始化第一个球的位置
            end = position[0]
            # 已放置球的数量
            ball = 0
            # 遍历所有篮子
            for x in position:
                # 如果当前位置可以放球
                if x >= end:
                    ball += 1
                    end = x + mag
            # 检查是否所有球都已放置
            return ball >= m

        # 对位置进行排序
        position.sort()
        # 初始化二分查找边界
        left = 1
        # 右边界优化
        right = (position[-1] - position[0]) // (m - 1)
        # 执行二分查找
        while right >= left:
            mid = left + right >> 1
            # 检查当前mid是否能满足条件
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        # 返回最大的满足条件的磁力
        return left - 1

Explore

在这个问题中，磁力为0的情况意味着多个球可以放在同一个位置上，这违反了题目要求的至少保持一定磁力距离的设定。因此，磁力的最小有效值应该是1，即任意两球之间至少有一个单位的间隔，这样才符合题目的物理意义。

这个设定基于最均匀分布的情况，即假设所有球都均匀地分布在位置数组的最小值和最大值之间。这种情况下，每两个球之间的最大可能间隔就是(position[-1] - position[0])除以(m-1)。虽然实际情况可能由于位置的不连续性导致球不能完全均匀分布，但这个估计提供了一个合理的上界。实际上，这个值可能大于任何可行的磁力，但它确保了二分查找不会错过任何可能的解。

check函数通过尝试在每个可能的位置放置球来验证给定的磁力值是否可行。它从数组的第一个位置开始，每次放置一个球后，它将寻找下一个至少与当前位置大于或等于磁力值的位置来放置下一个球。这个过程重复直到所有球都被放置或者没有足够的空间放置剩下的球。通过这种方式，我们确保了每对球之间的距离至少为给定的磁力值，同时尽可能用尽所有的空间（即尽可能地让磁力值大）。

虽然当前的mid值已经可以满足条件，但我们的目标是寻找最大可能的磁力。因此，即使当前的mid值可行，我们也希望探索是否存在更大的磁力值同样可行。通过将左边界设置为mid + 1，我们继续在可能的更大磁力值范围内进行搜索。一旦发现更大的磁力值不可行，二分查找将结束，此时的left - 1将是最大的可行磁力值。