⚡Flashcard Drill➔
NeetCode #302LC-774HardBinary Search
← Back to All Problems

#302 · #774 · Minimize Max Distance to Gas Station(最小化加油次数)

📌 Problem Statement & Constraints

You are given a sorted array stations of gas station positions and an integer k. You may add k new stations anywhere. Return the smallest possible maximum distance between adjacent stations after adding them. Answers within 10^-6 are accepted. Constraints: 10 <= stations.length <= 2000, 0 <= stations[i] <= 10^8, 1 <= k <= 10^6.

💡 Core Algorithmic Approaches

  1. Binary search on the maximum gap d: "can we achieve a maximum gap of at most d with at most k new stations" is monotone.
  2. For a gap g, the number of new stations needed is ceil(g / d) - 1.
  3. Because the answer is a real number, run a fixed number of iterations (about 100) instead of looping on lo < hi.
  4. The search range is [0, stations[-1] - stations[0]].

💻 Benchmark Python3 Implementation

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        import math

        def needed(d: float) -> int:
            total = 0
            for i in range(1, len(stations)):
                gap = stations[i] - stations[i - 1]
                # ceil(gap / d) - 1 new stations; the epsilon guards exact division
                total += max(0, math.ceil(gap / d - 1e-9) - 1)
            return total

        lo, hi = 0.0, float(stations[-1] - stations[0])
        for _ in range(100):               # enough iterations for 1e-6 precision
            mid = (lo + hi) / 2
            if needed(mid) <= k:
                hi = mid                   # feasible -> try a smaller gap
            else:
                lo = mid
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * iterations) = O(100n): each feasibility check is a linear scan.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using int(gap / d) for the station count: that gives floor(gap/d), but the requirement is ceil(gap/d) - 1. They differ exactly when gap is a multiple of d.
  • Omitting the epsilon: floating-point rounding can make an exact division appear slightly above or below the integer, producing an off-by-one.
  • Looping while hi - lo > 1e-6: workable, but a fixed iteration count is more predictable and equally accurate.
  • Setting the lower bound to a small positive number: a gap of 0 is the theoretical minimum, so lo = 0.0 is the right starting point.
  • Forgetting that new stations can be placed anywhere: the greedy count per original gap is valid because each gap is independent.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems

中文速览与面试要点

最小化加油次数

(经典问题「Minimize Max Distance to Gas Station」)给你一个整数数组 stations 表示水平数轴上的加油站位置,以及一个整数 k。你可以在任意位置添加 k 个新的加油站。请你返回添加加油站后, 相邻加油站之间的最大距离 的最小可能值。约束:10 ≤ stations.length ≤ 2000;0 ≤ stations[i] ≤ 10^8;stations 严格递增;1 ≤ k ≤ 10^6;答案与标准答案误差在 10^−6 以内即可。

核心要点

  • 二分答案(浮点二分)(标准解) :二分「相邻加油站最大距离的上限 d」,判定「能否用不超过 k 个新加油站使所有间隔 ≤ d」。
  • 判定函数 :对每个间隔 gap = stations[i+1] − stations[i] ,需要插入 ceil(gap / d) − 1 个新站。累加后判断是否 ≤ k。
  • 单调性 :d 越大,所需新站越少,因此可以二分(求最小值)。
  • 浮点二分固定迭代 100 次 :比用 while r − l &gt; eps 更稳定,且 100 次已远超 double 精度极限。
  • 答案范围 : [0, stations[-1] − stations[0]] 。

常见陷阱

  • 用 while r - l &gt; 1e-6 作为循环条件 :可能因浮点误差迭代次数不稳定;固定 100 次迭代更稳健且精度更高。
  • 判定中 int(gap / d) 的取整语义 :这是「需要插入的站数」的常用近似(把间隔分成 gap/d 段需要约 gap/d − 1 个新站,此处用 int(gap/d) 略有偏差但在 10^−6 容差下不影响)。更严格的写法是 math.ceil(gap / d) - 1 。
  • 二分方向写反 :本题求「最小上限」,应写 if feasible: r = mid else: l = mid 。
  • 初始上界写成 10^8 :虽然正确但精度收敛更慢;取 stations[-1] − stations[0] 更紧。
  • cnt 累加时忘记提前退出 :k 可达 10^6,提前退出可显著提速。

参考实现

class Solution:
    def minmaxGasDist(self, stations: list[int], k: int) -> float:
        def feasible(d: float) -> bool:
            """所有间隔 <= d 所需的新加油站数是否 <= k。"""
            cnt = 0
            for i in range(len(stations) - 1):
                gap = stations[i + 1] - stations[i]
                cnt += int(gap / d)     # 需要插入的站数
                if cnt > k:
                    return False
            return cnt <= k

        l, r = 0.0, float(stations[-1] - stations[0])
        for _ in range(100):            # 浮点二分:固定迭代次数
            mid = (l + r) / 2
            if feasible(mid):
                r = mid                 # 可行 -> 尝试更小的上限
            else:
                l = mid
        return l