1552. Magnetic Force Between Two Balls

题目信息

题号:

1552

难度:

Medium

主题:

排序、二分查找、贪心

原题:

LeetCode 1552

重点:

从给定篮子位置中放置 m 个球,每篮至多一个;最大化任意两球距离的最小值

题目重述

给定互不相同的整数位置数组 position 和整数 m。需要选择 m 个位置放置球,每个位置至多放一个球。

任意两球之间的磁力定义为它们位置差的绝对值。请最大化所有球对磁力中的最小值,并返回这个最大可能值。

2 <= m <= position.length <= 10^5,1 <= position[i] <= 10^9。

自建示例

最优放置需要平衡相邻球之间的距离:

输入:position = [1,2,8,12], m = 3
输出:4
解释:选择 1、8、12 时最小距离为 4,无法让三个球的最小距离更大。

只放两个球时选择最远的两个位置:

输入:position = [1,5,9], m = 2
输出:8
解释:把球放在 1 和 9,距离为 8。