LeetCode 1552. 两球之间的磁力

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 排序 二分查找

题目描述

✅ 1552. 两球之间的磁力

image-20260929085258803

image-20260929085258896

题意分析

给定若干不同的整数篮子位置，要从中选择 m 个放球，每个选中篮子放一个球。两球之间的磁力定义为位置距离，要求所有球对中最小的距离尽可能大。

求这个最大的最小距离，不是让总距离或最远两球距离最大。题目保证 2 <= m <= n，位置互不相同，因此至少可以做到相邻所选距离为一。

解法：二分答案 + 贪心验证

核心思路

[!blue]

先排序位置。对于按位置顺序放好的球，任意非相邻两球的距离都是中间若干相邻间距之和，因此只要相邻已放球的距离都至少为 d，所有球对就都满足要求。

固定候选 d 后，从最左篮子放第一球，再总是选择距离上一球至少为 d 的最早位置。这个贪心能放最多球：逐个比较任意合法方案，贪心第一球不会更晚；如果贪心前一球不晚于方案前一球，那么方案的下一位置对贪心也仍满足距离限制，所以贪心找到的最早可用下一位置也不会更晚。归纳下来，贪心不会比任何方案更早耗尽可选空间。

因此扫描能放下至少 m 个球，就证明距离 d 可行；放不下，则其他摆法也不可能。只需检查是否达到数量，多余篮子可以不用。

距离可行时，更小的距离也可行；不可行时，更大的也不可行。候选范围下界为一，上界为最右与最左篮子之差，二分寻找最后一个可行整数。

使用上中位数：可行时令 left = mid 保留它并继续向右，不可行时令 right = mid - 1。上中位数保证区间只差一时仍能缩小，不会卡在左端。边界重合时就是最大可行距离。

解题步骤

  1. 将位置升序排序，初始化距离范围 [1, maxPosition - minPosition]。
  2. 两界不同就取上中位数作为候选距离。
  3. 贪心判定时先放最左一球，之后只在与上个已放位置相距足够时放新球。
  4. 数量达到 m 即可判为可行；只有实际放球时才更新上个位置。
  5. 可行保留中点作为左界，不可行移低右界，最终返回重合值。

代码实现

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);

        int left = 1;
        int right = position[position.length - 1] - position[0];

        while (left < right) {
            // 使用上中位数，可行时保留中点也能让区间收敛。
            int mid = left + (right - left + 1) / 2;

            if (canPlace(position, m, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canPlace(int[] position, int balls, int distance) {
        int placed = 1;
        int last = position[0];

        for (int i = 1; i < position.length; i++) {
            // 尽早放下下一球，间距恰好满足也可以选择。
            if (position[i] - last >= distance) {
                placed++;
                // 只有真正放球后才更新上一个落点。
                last = position[i];

                if (placed == balls) {
                    return true;
                }
            }
        }

        return placed >= balls;
    }
}

import "sort"

func maxDistance(position []int, m int) int {
    sort.Ints(position)

    left, right := 1, position[len(position)-1]-position[0]
    for left < right {
        // 使用上中位数，可行时保留中点也能让区间收敛。
        mid := left + (right-left+1)/2
        if canPlace(position, m, mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

func canPlace(position []int, balls int, distance int) bool {
    placed := 1
    last := position[0]
    for i := 1; i < len(position); i++ {
        // 尽早放下下一球，间距恰好满足也可以选择。
        if position[i]-last >= distance {
            placed++
            // 只有真正放球后才更新上一个落点。
            last = position[i]
            if placed == balls {
                return true
            }
        }
    }
    return placed >= balls
}

复杂度分析

  • 时间复杂度：$O(n\log(n+1)+n\log(D+1))$，其中 $D$ 为最大位置差。先排序，每次二分判定再线性扫描位置。
  • 空间复杂度：二分和贪心判定额外为 $O(1)$，排序自身工作区另计；当前实现会将输入数组排序。

关键点总结

[!green]

  • 排序后相邻间距满足阈值，就能保证所有球对距离满足阈值。
  • 每个球尽早放置，不会减少后续球的可选空间，保证判定正确。
  • 距离阈值具有单调性，二分的是最后一个可行距离。
  • 可行时保留中点，配合上中位数才能确保推进。

易错点总结

[!yellow]

  • 距离恰好等于候选阈值也合法，判定应使用大于或等于。
  • 没放球也更新 last，会把距离参照点改成无关篮子，漏掉可行摆法。
  • 使用下中位数却令 left = mid，可能在相邻边界间不再前进。
  • 不能直接将总跨度除以球数当作答案，因为中间所需篮子位置未必存在。
  • 输入顺序不代表空间顺序，必须先排序再进行最早位置贪心。

相似题目

题目 难度 关联与区别
774. 最小化去加油站的最大距离 困难 两题都在一维位置上优化间距，原题增加站点最小化最大间隔，本题选择位置最大化最小间隔。
1482. 制作 m 束花所需的最少天数 中等 同样二分候选阈值，再通过贪心扫描判断能否形成足够数量的选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/43455993
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！