【Leetcode 每日一题】1552. 两球之间的磁力

问题背景

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

数据约束

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

解题过程

最小化最大值，考虑二分答案法。
和 扩展题 几乎完全一致，直接修改代码都能通过。

具体实现

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1;
        int right = (position[position.length - 1] - position[0]) / (m - 1) + 1;
        while (left < right) {
            int mid = left + ((right - left) >>> 1);
            if (check(position, mid) >= m) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

    private int check(int[] position, int power) {
        int res = 1;
        int pre = position[0];
        for (int item : position) {
            if (item >= pre + power) {
                res++;
                pre = item;
            }
        }
        return res;
    }
}