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
- Binary search on the maximum gap
d: "can we achieve a maximum gap of at mostdwith at mostknew stations" is monotone. - For a gap
g, the number of new stations needed isceil(g / d) - 1. - Because the answer is a real number, run a fixed number of iterations (about 100) instead of looping on
lo < hi. - 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 givesfloor(gap/d), but the requirement isceil(gap/d) - 1. They differ exactly whengapis a multiple ofd. - 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.0is 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.
🧩 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 > eps 更稳定,且 100 次已远超 double 精度极限。
- 答案范围 : [0, stations[-1] − stations[0]] 。
常见陷阱
- 用 while r - l > 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