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

2022-03-07 HGNULB 约 15 分钟

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

分类

题目描述

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

题意分析

数轴上给定 $n$ 个严格递增的加油站位置 stations，现在允许再新增最多 $k$ 个加油站（位置可以是任意实数，不必是整数），目标是让「相邻两个加油站之间的最大距离」尽可能小，返回这个最小的最大距离。答案与标准值相差不超过 $10^{-6}$ 即视为正确。

「最小化最大值」这个措辞是最强的信号。它意味着答案本身是一个可以被拿出来单独检验的量：给定一个候选距离 $D$，我们能独立地回答「有没有办法用不超过 $k$ 个新站，把所有相邻间距都压到不超过 $D$」。而且这个检验具有单调性——$D$ 越大越容易满足。凡是「最小化最大值」「最大化最小值」，第一反应就应该是把「求最优值」翻译成「判定某个值可行与否」。

第二个要读准的点：新站的位置是连续的实数，不是整数格点。这直接决定了答案是一个实数（例如把长度 1 的间隔一分为二，答案就是 0.5），所以二分必须在浮点数上做，任何整数二分都会给出错误结果。同时也意味着一个长度为 $g$ 的间隔要插入 $m$ 个站时，最优摆法一定是等分，此时最大子段长度恰好是 $g/(m+1)$，没有更好的摆法。

第三，只有相邻已有加油站之间的间隔需要被填充。数轴上第一个站之前和最后一个站之后不构成「相邻加油站之间的距离」，不能往那里放站，那是白白浪费名额。

约束方面：$10 \le n \le 2000$，$0 \le stations[i] \le 10^8$，$1 \le k \le 10^6$。$k$ 高达百万而位置最大 $10^8$，说明单次可行性检查里累加出来的「需要新增的站数」可能非常巨大，中间量的溢出必须提前防住。$n$ 只有两千，每次检查扫一遍是 $O(n)$，配合几十次二分完全不构成压力。

边界方面：$k$ 用不完是允许的（题目说的是「最多」）；答案的下界是 0（$k$ 无限大时可以无限细分），上界是原始的最大间隔（一个站都不加时的答案）。这两个值恰好构成二分的初始区间。

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

核心思路

先看直接构造的思路：每次找出当前最长的那个间隔，往里面插一个站，重复 $k$ 次。这个贪心需要一个优先队列，每次取出最大间隔、拆分后放回，复杂度是 $O(k \log n)$。$k$ 到 $10^6$ 时勉强能跑，但它有个致命问题——每次只插一个站，而最优解可能要求某个间隔一次性插入几十万个站，堆里的元素要被反复取出放回，常数极大且逻辑容易写错。更本质地说，这个贪心是在「构造答案」，而我们其实只需要「知道答案是多少」。

换成判定视角。定义谓词 $can(D)$：「是否存在一种放置方案，使用不超过 $k$ 个新站，让所有相邻间距都不超过 $D$」。

这个谓词可以在 $O(n)$ 内精确算出。对每一个原始间隔 $g = stations[i] - stations[i-1]$，要把它切成若干段且每段长度不超过 $D$，最少需要切成 $\lceil g / D \rceil$ 段——因为 $m$ 段的最大长度至少是 $g/m$，要让 $g/m \le D$ 就必须 $m \ge g/D$，而段数是整数所以向上取整；反过来等分成 $\lceil g/D \rceil$ 段时每段长度恰为 $g / \lceil g/D \rceil \le D$，可以达到。切成 $m$ 段需要 $m - 1$ 个新站，所以这个间隔的最小代价是 $\lceil g / D \rceil - 1$。各间隔互不影响，把代价相加就是总需求 $need(D)$，于是

$can(D)$ 为真 $\iff need(D) \le k$，其中 $need(D) = \sum_i \left( \lceil g_i / D \rceil - 1 \right)$。

单调性也随之明确：$D$ 增大时每个 $\lceil g_i / D \rceil$ 不增，所以 $need(D)$ 单调不增，$can(D)$ 一旦为真则对更大的 $D$ 恒为真。这正是二分的前提。我们要找的答案，就是使 $can$ 为真的最小 $D$。

二分区间怎么定：下界取 0，因为距离非负且当 $k$ 足够大时答案可以任意接近 0；上界取原始最大间隔 $\max_i g_i$，因为一个站都不加时的最大间距就是它，$can(\max g_i)$ 必然为真（此时每个间隔的 $\lceil g_i/D \rceil$ 都是 1，$need = 0$）。答案必落在 $[0, \max g_i]$ 内。

浮点二分的收敛方式与整数二分不同：不能用「区间为空」作终止条件（浮点区间永远不会空，会死循环），而应固定迭代次数。每次迭代把区间宽度减半，初始宽度不超过 $10^8$，迭代 60 次后残余误差约为 $10^8 / 2^{60} \approx 10^{-10}$，远小于要求的 $10^{-6}$。固定次数的写法既避免了死循环，也免去了对精度阈值的调参。

循环中维持的不变量是：$left$ 始终落在不可行侧（或初始的 0），$right$ 始终落在可行侧。所以每次 $can(mid)$ 为真时收缩 $right = mid$，为假时推进 $left = mid$，最终返回 $right$——它是我们确认过的、可行的那一侧。

最后一处工程细节：$need$ 的累加要边加边判，一旦超过 $k$ 立刻返回假。当 $mid$ 极小时（二分后期可能小到 $10^{-10}$ 量级），单个 $\lceil g/D \rceil$ 就能达到 $10^{18}$ 级别，把两千个这样的数累加进一个 32 位整数必然溢出成负数，反而被误判为可行。提前短路既省时间，更是正确性的保障。

解题步骤

第一步，扫一遍数组求出原始最大间隔，作为二分上界 $right$，并令下界 $left = 0$。 为什么上界取最大间隔而不是取整条路的总长：总长虽然也是合法上界，但会让初始区间变宽、同样的迭代次数下精度变差；更重要的是最大间隔有明确语义——它就是「一个站都不加」的答案，让区间的两端都有物理含义。

第二步，固定迭代 60 次，每次取 $mid = (left + right) / 2$。 为什么用固定次数而不是 while (right - left > eps)：浮点区间在极端情况下可能因为舍入而永远不满足退出条件，导致死循环；固定次数是浮点二分的标准写法。为什么是 60 次：初始宽度 $\le 10^8$，每次减半，$10^8 / 2^{60}$ 已经远小于 $10^{-6}$ 的精度要求，留足了余量。

第三步，调用 $can(mid)$，为真则 $right = mid$，为假则 $left = mid$。 为什么真的时候收缩右端：我们要找的是最小的可行值，可行说明答案不会比 $mid$ 更大，可以把搜索范围压到左半边。方向写反会收敛到最大可行值（也就是初始上界），完全错误。

第四步，在 $can$ 内部遍历每个相邻间隔，累加 $\lceil g / D \rceil - 1$。 为什么是向上取整再减一：$\lceil g/D \rceil$ 是段数的下界，段数减一才是新增站数。少减这个 1，每个间隔都会虚增一个名额，总需求被高估 $n-1$，答案偏大。

第五步，累加过程中一旦 $need > k$ 就立刻返回假。 为什么必须提前返回：$mid$ 很小时单个间隔的需求就能溢出 32 位整型，累加后变成负数，need <= k 反而成立，把不可行的 $D$ 判成可行，二分收敛到一个错得离谱的小值。为什么判断用严格大于：$need = k$ 意味着名额恰好用完，是可行的，用 $\ge$ 会把这种临界情况误判为不可行。

第六步，循环结束返回 $right$。 为什么返回 $right$ 而不是 $left$：不变量规定 $right$ 一直落在可行侧。60 次迭代后两者已相差 $10^{-10}$ 量级，实践上都能通过，但返回 $right$ 才是语义正确的。

以 stations = [1,2,3,4,5,6,7,8,9,10]、k = 9 走一遍。共 9 个间隔，每个长度都是 1，所以 $right$ 初值为 1，$left = 0$。

第 1 次迭代：$mid = 0.5$。检查 $can(0.5)$：每个间隔需要 $\lceil 1 / 0.5 \rceil - 1 = 2 - 1 = 1$ 个新站，9 个间隔合计 $need = 9$。$9 > 9$ 不成立，返回真。收缩 $right = 0.5$。此时区间变为 $[0, 0.5]$。

第 2 次迭代：$mid = 0.25$。$\lceil 1 / 0.25 \rceil - 1 = 4 - 1 = 3$，累加到第 3 个间隔时 $need = 9$，还不超；第 4 个间隔后 $need = 12 > 9$，立即返回假。推进 $left = 0.25$，区间变为 $[0.25, 0.5]$。这一步正好展示了提前返回的作用：只扫了 4 个间隔就得出结论，没有把 9 个全算完。

第 3 次迭代：$mid = 0.375$。$1 / 0.375 \approx 2.667$，向上取整为 3，每个间隔需 2 个新站，9 个间隔合计 18，超过 9，返回假。$left = 0.375$。

第 4 次迭代：$mid = 0.4375$。$1 / 0.4375 \approx 2.286$，向上取整仍是 3，每个间隔仍需 2 个，合计 18 > 9，返回假。$left = 0.4375$。

第 5 次迭代：$mid = 0.46875$。$1 / 0.46875 \approx 2.133$，向上取整 3，同样返回假。$left = 0.46875$。

后续迭代持续从下方逼近 0.5：只要 $mid < 0.5$，$1/mid > 2$，向上取整就是 3，每个间隔需要 2 个站、总需求 18，恒不可行；而 $mid = 0.5$ 时恰好 $1/mid = 2$，取整仍是 2，总需求 9，恰好用完名额。所以 $right$ 从第一次迭代后就锁定在 0.5 再未变过，$left$ 一路向 0.5 收敛。

60 次迭代结束，返回 $right = 0.5$。含义是：在每个长度为 1 的间隔正中各插一个站，全部 9 个名额刚好用完，所有相邻间距都变成 0.5，而任何比 0.5 更小的目标都需要至少 18 个站，超出预算。这个例子还顺带说明了为什么 $need > k$ 必须用严格大于——$need = 9 = k$ 正是答案所在的那个临界点，误判成不可行就会得到 1.0。

代码实现

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

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(n \log \frac{R}{\varepsilon})$，本题固定为 $O(60n)$。求初始上界扫一遍是 $O(n)$；随后 60 次迭代，每次的可行性检查最坏扫遍全部 $n-1$ 个间隔、每个间隔只做一次除法和取整。$n \le 2000$ 时总计约 $1.2 \times 10^5$ 次浮点运算，几乎瞬时。相比「用优先队列逐个插站」的 $O(k \log n)$（$k$ 可达 $10^6$），二分答案与 $k$ 的大小完全无关，这是它在本题上的决定性优势。

空间复杂度：$O(1)$。只用了 $left$、$right$、$mid$、$need$ 几个标量，没有任何与输入规模相关的辅助结构。注意 $need$ 虽然是标量，但它的取值范围才是真正需要留心的地方——提前返回把它牢牢压在 $k$ 附近。

关键点总结

「最小化最大值」直接翻译成「判定 + 二分」。求最优值难，判定某个值是否可行往往容易得多。写下谓词 $can(D)$、验证它关于 $D$ 单调、然后在答案空间上二分，这套三步法可以原样套用到分割数组、船运载重、吃香蕉速度等一整类题目上。

判定函数要给出「最小代价」而不是「某种代价」。本题的 $\lceil g/D \rceil - 1$ 是把间隔切到达标所需的最少站数，且等分摆法能取到这个下界。判定函数如果算的不是最优代价，单调性和正确性都会崩。写完判定后要习惯性问一句：这个代价是可达的下界吗。

答案是实数就必须浮点二分，且用固定迭代次数。整数二分会把 0.5 这样的答案舍成 1。浮点二分不能用区间为空作终止条件，固定次数（本题 60 次）既保证精度又杜绝死循环，还省去了 eps 的调参。所需次数可以直接算：$\log_2(初始宽度 / 目标精度)$。

判定函数内部的中间量要提前短路。$k$ 达到 $10^6$、位置达到 $10^8$、$mid$ 可以小到 $10^{-10}$，三者相乘就是溢出。累加时一旦超过阈值立刻返回，既是剪枝也是防溢出。凡是「累加计数再与上限比较」的判定，都应该写成边加边判。

二分区间的两端要有物理含义。下界 0 对应「无限多个站」，上界最大间隔对应「一个站都不加」，两端都是显然可行或显然不可行的极端。这样定区间不容易漏掉答案，也便于向面试官解释。

面试视角：面试官最想听到的是「为什么可以二分」，即单调性的论证——$D$ 变大，每个间隔的需求单调不增，总需求单调不增。第二个高频追问是「$\lceil g/D \rceil - 1$ 怎么来的」，要能说清「$m$ 段的最大长度至少 $g/m$」这个下界和「等分可达」这个上界。第三个是「为什么不用堆贪心」，答案是复杂度与 $k$ 挂钩、$k$ 高达 $10^6$，而二分与 $k$ 无关。如果被追问精度，要能当场算出 60 次迭代的残余误差量级。主动指出「$need$ 要防溢出」通常能显著加分，因为这说明你考虑过 $mid$ 趋近于 0 时的极端情形。

易错点总结

错误写法：用整数二分，mid = (left + right) / 2 中 left、right 都是 int。以 stations = [1,2,3,4,5,6,7,8,9,10]、k = 9 为例，整数区间只有 0 和 1 两个候选，$can(0)$ 无意义（除以 0），最终返回 1.0，而正确答案是 0.5。新站位置是实数，答案也必然是实数。

错误写法：判定内部写成 need >= k 就返回假。以 stations = [1,2,3,4,5,6,7,8,9,10]、k = 9 为例，$D = 0.5$ 时 $need$ 恰好等于 9，被误判为不可行，二分收敛到 1.0，而正确答案是 0.5。名额刚好用完是允许的，必须用严格大于。

错误写法：忘记减 1，直接累加 $\lceil g / D \rceil$。以 stations = [1,2,3,4,5,6,7,8,9,10]、k = 9 为例，$D = 0.5$ 时每个间隔算成 2，合计 18 > 9 被判不可行；实际上答案 0.5 是可达的。段数与新增站数差 1，这个 1 乘上 $n-1$ 个间隔会造成巨大偏差。

错误写法：用向下取整或直接 (int)(g / D)。以 stations = [0,1,2,3,4,5,6,7,8,9]、k = 0 为例，$D = 0.9$ 时正确需求是 $\lceil 1/0.9 \rceil - 1 = 1$ 每间隔、合计 9 > 0 不可行；向下取整得到 $1 - 1 = 0$，误判为可行，二分一路收敛到接近 0 的值，而正确答案是 1.0。

错误写法：二分方向写反，可行时 left = mid。以任意输入为例，$can$ 为真时把下界抬高，等于在「可行区间」里继续往大的方向找，最终收敛到初始上界（原始最大间隔），也就是「一个站都不加」的答案，$k$ 完全没被利用。

错误写法：累加 $need$ 时不提前返回。以 stations 中存在长度 $10^8$ 的间隔为例，二分后期 $mid$ 可能小到 $10^{-10}$，单个间隔的需求就达到 $10^{18}$；Java 里 (int) Math.ceil(...) 会饱和成 Integer.MAX_VALUE，两千个这样的值累加进 int 直接溢出成负数，need > k 永远不成立，不可行的 $D$ 被判成可行，答案收敛到接近 0 的错误值。

错误写法：终止条件用 while (right - left > 1e-6)。以初始区间宽度 $10^8$ 为例，浮点数在接近答案时的相邻可表示值间距可能大于或等于设定的 eps，循环无法退出而死循环；即使侥幸退出，$10^{-6}$ 的残余误差正好卡在判题容差边缘，容易被判错。固定迭代次数并留足余量才稳妥。

错误写法：迭代次数取得太少，例如 30 次。以 stations 跨度接近 $10^8$ 为例，30 次迭代后残余误差约 $10^8 / 10^9 \approx 0.1$，远超 $10^{-6}$ 的要求，直接判错。次数应按 $\log_2(初始宽度 / 精度)$ 估算并加保险。

错误写法：把首站之前和末站之后也当成需要填充的间隔。以 stations = [10,11,...,19] 为例，若额外考虑 0 到 10 这段「间隔」，会凭空消耗大量名额，$need$ 虚高，答案偏大。题目只关心相邻加油站之间的距离。

错误写法：上界初值取 stations[n-1] - stations[0]（整条路的长度）而迭代次数不变。以跨度 $10^8$ 但最大间隔只有 1 的输入为例，初始区间宽了八个数量级，60 次迭代后的残余误差随之放大，虽然本题仍能满足精度，但把这个习惯带到迭代次数更少的场景就会直接失精。上界应取真正的最大间隔。

错误写法：用优先队列贪心，每次取出最大间隔插一个站，循环 $k$ 次。以 $k = 10^6$、$n = 2000$ 为例，需要一百万次堆操作，且每次都要重新计算「插入 $m$ 个站后的等分长度」，实现复杂度和运行时间都远高于二分；更麻烦的是浮点比较让堆的顺序不稳定，容易出现细微偏差。

错误写法：can 里除法写成 gap / d 但 gap 用 int 且 d 也被误声明为 int。以 d 取值 0 的第一次迭代为例，Java 抛除零异常（整数除零），Go 直接 panic；即便 d 非零，整数除法也会截断掉小数部分，判定结果完全错误。间隔与候选距离都必须是浮点。

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	同为最小化最大值，但答案是整数且判定用贪心分段计数，无需浮点
875. 爱吃香蕉的珂珂	中等	二分速度、判定用 $\lceil pile / speed \rceil$ 求总小时，是本题的整数版入门题
1011. 在 D 天内送达包裹的能力	中等	二分载重，判定要顺序装箱且不可拆分，下界必须取单件最大重量
1552. 两球之间的磁力	中等	最大化最小间距，判定方向与本题相反，贪心地尽量靠左放球
1231. 分享巧克力	困难	最大化最小块甜度，判定是「能否切出至少 $k+1$ 块」，切分位置受限于原数组
644. 子数组最大平均数 II	困难	同样是浮点二分，但判定要靠「减去候选均值后求最大子段和是否非负」的变换
719. 找出第 K 小的数对距离	困难	二分距离值，判定用双指针统计不超过该距离的数对个数，是「二分 + 计数」形态
668. 乘法表中第 k 小的数	困难	二分数值并逐行统计不超过它的个数，判定函数是数学计数而非贪心构造
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定要扫描连续可用段并整除累计束数，注意无解时的返回值
69. x 的平方根	简单	最基础的二分答案，判定就是一次乘法比较，可用来体会「在答案空间上搜索」