LeetCode 1552. 两球之间的磁力

2021-09-10 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1552. 两球之间的磁力

题意分析

给定一排位置互不相同的篮子和 m 个球，每个篮子最多放一个球。任意两球之间的「磁力」定义为它们位置之差的绝对值，题目要求最大化「所有球对之间磁力的最小值」。返回的是这个最小值能达到的最大数值，不需要给出具体的放置方案。

「所有球对的最小磁力」这句话可以先化简：把球按位置排序后，任意两球的距离一定不小于它们之间相邻球对的距离之和，所以全局最小值必然出现在某一对相邻球上。于是目标简化成「最大化相邻球间距的最小值」，这是典型的最大化最小值结构。

输入里的位置是无序的，必须先排序，否则「相邻」这个概念都无从谈起。

规模上篮子数可到 $10^5$，位置值可到 $10^9$。枚举所有放置方案是组合级的，完全不可能；而位置值域高达 $10^9$ 说明答案本身的取值空间巨大，只能在值域上做对数级的搜索，逐个试是不行的。

边界上 m 至少是 2，所以答案至少是 1（两个不同篮子的距离至少为 1）；m 最大等于篮子数，此时所有篮子都要放球，答案就是排序后相邻篮子间距的最小值。答案的上界是最远两个篮子的距离，因为再大的话连两个球都放不下。

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

核心思路

这是“最大化最小值”：直接构造最优放法困难，但可以判断候选距离 distance 是否可行。若某个距离可行，更小的距离一定可行；若不可行，更大的距离也不可能可行，因此答案具有单调边界，可以二分最后一个可行值。

判定前先排序。把第一个球放在最左篮子，之后从左到右遇到距离上一个球至少为 distance 的位置就立即放置。这个贪心能放下该距离约束下最多的球：任意合法方案的第一个球都可左移到最左位置；假设前 k-1 个球已不晚于某合法方案，第 k 个贪心位置又是满足距离的最早位置，也不会晚于该方案。逐个交换后球数不减。

判定不变量：扫描到任意位置时，last 是贪心已放最后一个球的位置，并且这些球在所有同数量合法前缀方案中位置逐个最靠左。 因此扫描结束能放至少 m 个球，当且仅当候选距离可行。

二分维护：left 始终可行，真正答案位于 [left,right]，而 right+1 一定超过当前可能范围。求最后一个可行值时使用上取整中点；可行令 left=mid，不可行令 right=mid-1。

解题步骤

升序排序 position。

二分区间设为 [1, maxPosition-minPosition]。

用上取整中点测试候选距离。

判定时从最左篮子开始贪心放球；放够 m 个即可返回 true。

二分收敛后返回 left。

对 [1,2,3,4,7]、m=3，距离 3 可放在 1,4,7，距离 4 最多放两个球，所以答案为 3。边界 m=2 时最优就是最左与最右位置的距离。

代码实现

import java.util.Arrays;

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
}

复杂度分析

设篮子数为 n，坐标跨度为 D。

时间复杂度： $O(n\log n+n\log D)$。排序后，二分每轮进行一次线性判定。

空间复杂度： 除标准库排序所需空间外为 $O(1)$；排序通常使用 $O(\log n)$ 级别的栈空间。

关键点总结

“最大化最小值”优先考虑对答案做二分，前提是先证明可行性单调。

固定距离后，每次选择最早合法位置，为后续保留最大空间。

判定只需关心相邻已放球的距离；非相邻球距离只会更大。

最后一个可行值模板使用上取整中点和 left=mid。

能放至少 m 个就可行，多余球可以撤掉且不会降低剩余间距。

易错点总结

忘记排序： 贪心扫描和坐标差都失去意义。

中点下取整却仍写 left=mid： 区间剩两个值时可能死循环。

判定要求 placed==m 且继续扫描到底： 贪心可能放出更多球；放够时应直接成功，或最终判断 >=m。

使用严格大于候选距离： 恰好等于的合法位置会被漏掉。

放球后不更新 last： 后续距离会错误地一直相对第一个球计算。

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	最小化最大速度，验证函数是上取整除法求总耗时，二分方向与本题相反
1011. 在 D 天内送达包裹的能力	中等	元素顺序不可打乱，验证时按容量顺序切段，下界是单个元素最大值
410. 分割数组的最大值	困难	同一问题也可用区间动态规划求解，适合对比二分与动规两条路线
1231. 分享巧克力	困难	最大化最小段和，与本题同为最大化最小值，验证时累加而非比距离
1482. 制作 m 束花所需的最少天数	中等	二分的是时间轴，验证要数连续可用段的数量，还需处理无解返回 -1
774. 最小化去加油站的最大距离	困难	答案是实数，二分要按精度而非整数收敛，循环终止条件完全不同
719. 找出第 K 小的数对距离	困难	二分距离后用双指针统计不超过该距离的数对，验证从贪心换成计数
668. 乘法表中第k小的数	困难	在虚拟矩阵的值域上二分，验证靠逐行整除计算不超过候选值的元素个数
878. 第 N 个神奇数字	困难	验证函数由容斥与最小公倍数给出，还要对结果取模
LCP 12. 小张刷题计划	中等	验证时每天可免费跳过一题，贪心里多了一个「扣掉当前最大值」的细节