LeetCode 1552. 两球之间的磁力

Categories:

题目描述
思路分析
1. 解法一：二分答案 + 贪心验证（推荐）
相似题目

题目描述

✅ 1552. 两球之间的磁力

思路分析

解法一：二分答案 + 贪心验证（推荐）

核心思路：

对”最小磁力”（即相邻球之间距离的最小值）进行二分搜索，答案范围为 [1, positions[n-1] - positions[0]]

对于每个候选答案 mid，用贪心策略验证：将第一个球放在最左边的篮子，之后每次找到距离上一个球不小于 mid 的最近篮子放球

如果能放下 m 个球，说明 mid 可行，尝试更大的值；否则缩小范围

先对 positions 排序，使贪心策略可以从左到右线性扫描

复杂度分析：

时间复杂度：O(n log n + n log D)，其中 n 为篮子数量，D 为最大距离差

空间复杂度：O(log n)，排序的递归栈空间

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;
    }

    // 贪心验证：以最小间距 minDist 能否放下 m 个球
    private boolean canPlace(int[] position, int m, int minDist) {
        int count = 1;
        int last = position[0];

        for (int i = 1; i < position.length; i++) {
            if (position[i] - last >= minDist) {
                count++;
                last = position[i];
            }
        }

        return count >= m;
    }
}

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
}

// 贪心验证：以最小间距 minDist 能否放下 m 个球
func canPlace(position []int, m, minDist int) bool {
    count := 1
    last := position[0]

    for i := 1; i < len(position); i++ {
        if position[i]-last >= minDist {
            count++
            last = position[i]
        }
    }

    return count >= m
}

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分答案
1011. 在 D 天内送达包裹的能力	中等	二分答案
410. 分割数组的最大值	困难	二分答案
774. 最小化去加油站的最大距离	困难	二分答案
2560. 打家劫舍 IV	中等	二分答案 + 贪心
1760. 袋子里最少数目的球	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/43455993