「力扣」第 1552 题：两球之间的磁力（中等）

• 题目链接：1552. 两球之间的磁力 (opens new window)

题意分析：距离这件事情天然具有连续性，并且距离肯定是正数。并且题目都告诉我们要我们求「最大化的最小磁力」，很显然往「最大值极小化」这一类问题上靠。

分析单调性和左右逼近留给读者。

参考代码：

import java.util.Arrays;

public class Solution {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int len = position.length;
        int left = 1;
        int right = position[len - 1] - position[0];

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (countSplits(position, mid) >= m) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private int countSplits(int[] position, int distance) {
        int len = position.length;
        int pre = position[0];

        int M = 1;
        for (int i = 1; i < len; i++) {
            if (position[i] - pre >= distance) {
                M++;
                pre = position[i];
            }
        }
        return M;
    }
}

import java.util.Arrays;

public class Solution {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int len = position.length;
        int left = 1;
        int right = position[len - 1] - position[0];

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 最小磁力太小，使得分割数 countSplits 变多，应该考虑增大最小磁力
            // 关键：等于的时候，要考虑增大最小磁力，使得分割数还是这么多
            if (countSplits(position, mid) >= m) {
                // 下一轮搜索区间是 [mid, right]
                left = mid;
            } else {
                // 下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            }
        }
        return left;
    }

    private int countSplits(int[] position, int distance) {
        int len = position.length;
        int pre = position[0];

        // 需要使用的篮球数
        int count = 1;
        for (int i = 1; i < len; i++) {
            if (position[i] - pre >= distance) {
                count++;
                // 注意：记录上一个篮球的位置
                pre = position[i];
            }
        }
        return count;
    }
}

• 要返回的是最小磁力，先找到最小磁力的 最小可能取值 和 最大可能取值 ；
  • 最小可能取值，是 给定数组中距离最近的两个位置之间的磁力 ，所以需要先对数组进行排序，并遍历数组找到相邻两个位置的最小距离。
  • 最大可能取值，一共有 个球，所以有 个间隔，最大的可能取值是 最平均的取值 ，所以根据给定数组最大值与最小值之差与间隔数的比值计算出平均距离，就是给定的最大可能取值；

证明：假设有 个间隔，给定数组规定的篮子间最大距离为 ，那么最小磁力的最大可能取值是 。假设有某一可能取值 大于最大可能取值，那么所有距离都一定大于等于 ，此时假设 个间隔距离均为 ，总距离 ，也大于给定的最大距离，所以不成立。

对当前计算出的最小磁力进行验证。验证过程使用 贪心算法 。遍历数组，若找到两位置之间距离大于等于最小磁力，则计数值加 ，最后只需要判断总计数值是否大于等于给定间隔数 即可。

例如，示例1中，假设我们当前二分搜索计算出的距离为 2，那么我们遍历数组，假设第一个位置为 1，那么下一个找到的位置应该是3，因为 3 - 1 >= 2，计数值加1；再下面找到的是 7，因为 7 - 3 >= 2，计数值加1。此时数组遍历完成，总计数值为 2，而给定间隔数 m - 1 = 2，满足条件，说明最小磁力为2是可以做到的。但如果我们当前计算出的距离为4，那么第一个位置为1，找到的第二个位置就只能是7，数组遍历完成总计数值为1，小于给定间隔数，说明最小磁力为4是不成立的。

在判断计算值满足条件与否之后，我们要对二分搜索边界进行转化，由于题目要求的是最大化的最小磁力，所以若当前计算出的最小磁力满足条件，我们要将左边界右移，去判断稍大一点的数值是否满足条件；若当前计算出的最小磁力不满足条件，我们要将右边界左移，判断稍小的数值是否满足条件。

由于每次满足条件后左边界右移，所以左边界的左边一个数值是一定满足条件的，所以最后返回值为 left - 1，具体返回值根据边界移动的判定规则进行判断。