LeetCode 774. 最小化去加油站的最大距离

2022-03-07 HGNULB 约 5 分钟

文章信息 7 个分类 · 2 个标签

分类

LeetCode CodeTop 困难 未解决 会员题 1-2 网易

标签

数组 二分查找

题目描述

✅ 774. 最小化去加油站的最大距离

题意分析

已有站点按位置递增排列，可以在它们之间的任意实数位置增加 k 个站。让所有相邻站点间距的最大值尽可能小，返回满足精度要求的结果。

解法：二分答案 + 可行性检查

核心思路

[!blue]

不直接决定每个站放在哪里，而是先给定最大允许间距 d，判断能否用 k 个新站实现。对于长度为 gap 的原始间隔，若分成 m 段且每段都不超过 d，就必须有 m*d >= gap，所以最少段数为 ceil(gap/d)；将间隔等分成这么多段也确实可行。

分成 m 段需要新增 m-1 个站，因此这个间隔的最少需求为 ceil(gap/d)-1。各原始间隔互不影响，把需求相加得到 need。若 need > k，当前 d 不可行，而且后续间隔只会增加需求，可以立即停止检查；若 need <= k，剩余站点继续放入任意间隔只会缩短间距，因此即使题目要求恰好增加 k 个，也仍然可行。

d 越大，每段允许越长，所需新站越少，可行性从小到大只会由否变为是，适合二分答案。下界从 0 开始，上界取原始最大间距；这个上界不用增加站就可满足，一定可行。每次只检查正的中点：可行就把右界移到中点，不可行就把左界移到中点。

二分始终保留可行的右界，每轮将搜索区间宽度减半。代码固定执行 60 轮后返回右界，不使用整数二分的 mid+1 或 mid-1，从而保留实数答案的精度。

解题步骤

1. 求已有相邻站点的最大间距作为可行上界。
2. 计算中点 d，并累加各间隔的最少加站数。
3. 需求超过 k 则提高下界，否则降低可行上界。
4. 固定轮数后返回上界。

代码实现

class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        double left = 0.0;
        double right = 0.0;

        for (int i = 1; i < stations.length; i++) {
            right = Math.max(right, stations[i] - stations[i - 1]);
        }

        for (int t = 0; t < 60; t++) {
            double mid = (left + right) / 2;

            if (can774(stations, k, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return right;
    }

    private boolean can774(int[] stations, int k, double d) {
        int need = 0;

        for (int i = 1; i < stations.length; i++) {
            double gap = stations[i] - stations[i - 1];

            // 所需段数向上取整，新增站点比段数少一。
            need += (int) Math.ceil(gap / d) - 1;

            // 需求已超预算时即可否定，后续间隔只会增加需求。
            if (need > k) {
                return false;
            }
        }

        return true;
    }
}

import "math"

func minmaxGasDist(stations []int, k int) float64 {
    left := 0.0
    right := 0.0
    for i := 1; i < len(stations); i++ {
        gap := float64(stations[i] - stations[i-1])
        if gap > right {
            right = gap
        }
    }

    for t := 0; t < 60; t++ {
        mid := (left + right) / 2
        if can774(stations, k, mid) {
            right = mid
        } else {
            left = mid
        }
    }

    return right
}

func can774(stations []int, k int, d float64) bool {
    need := 0
    for i := 1; i < len(stations); i++ {
        gap := float64(stations[i] - stations[i-1])
        // 所需段数向上取整，新增站点比段数少一。
        add := int(math.Ceil(gap/d)) - 1
        need += add
        // 需求已超预算时即可否定，后续间隔只会增加需求。
        if need > k {
            return false
        }
    }
    return true
}

复杂度分析

• 时间复杂度：$O(60n)$，n 为原有站点数；固定二分 60 轮，每轮最多扫描 n-1 个间隔。
• 空间复杂度：$O(1)$。

关键点总结

[!green]

• 段数比新增站点数多一。
• 判定比较的是总需求是否不超过 k。
• 实数二分保持可行上界，最终输出该界。

易错点总结

[!yellow]

• 直接取 gap/d 的整数部分作为站点数：整除时会多算一个。
• 需求等于 k 时判为不可行：恰好用完预算仍然合法。
• 只拆分当前最大间隔一次：不能保证最终最大间距全局最小。
• 使用整数中点或 mid±1 更新边界：无法表达题目要求的实数答案。

相似题目

题目	难度	关联与区别
410. 分割数组的最大值	困难	同样二分最坏区间上限并计算需要多少次分割，本题答案为实数且可插入新站。
475. 供暖器	中等	同样最小化覆盖中的最坏距离，原题供暖器位置固定，本题可主动新增k个位置。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/14020587

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！