题干与适用场景
这是一个带资源约束的区间贪心题。车辆只能在已经经过的站点取油，油量决定下一次能否跨过更远的位置；目标是最少的加油站次数，不是总油量最少。面试中需要同时说明可达性、延迟决策、最大堆不变量和最后一段到终点的边界。
面试官考察什么
- 能否把“油量不足时才加油”转成延迟贪心。
- 能否证明从已经过站点中取最大油量不会增加最优次数。
- 能否正确处理起点、终点、同位置站点和不可达情况。
- 能否给出 O(n log n) 时间、O(n) 空间的实现，并解释堆操作。
回答前需要澄清的问题
确认站点是否严格按位置递增、同一位置是否可能有多个站点、油量是否为非负整数，以及是否把目标点视为可加油站。还要确认输入规模和整数范围，避免用固定宽度整数造成溢出。题目默认车辆在位置 0 出发，经过某站后才可使用该站燃油。
30 秒回答框架
按位置扫描站点，并把经过站点的燃油放入最大堆。每走到下一站或终点，就从当前燃油扣除距离；若燃油为负，说明必须从已经过的站点中补油，反复弹出最大值并增加次数。堆为空仍无法到达则返回 -1。每次补油都选择最大历史油量，等价于在当前必须增加一次停止时让可达距离增加最多，因此不会劣于其他选择。
分步骤深入解答
1. 建立可达性不变量
扫描到位置 p 时，堆保存所有位置不超过 p 的站点油量，当前 fuel 是尚未使用的燃油。若燃油小于零，不可能继续向前，必须从堆中选择已经经过的站点。每弹出一个油量，当前可达范围增加该油量，直到燃油恢复为非负。
2. 证明延迟贪心
假设某个最优方案在需要补油时选择了较小的已经过油量 a，而堆中还有更大的 b。把这次选择替换为 b，停止次数不变，当前位置之后的剩余油量不减，因此后续路线仍可行。重复交换后，可得到总是选择最大油量的同样优的方案，所以最大堆满足最少次数目标。
3. 统一扫描终点边界
把终点 target 当作一个油量为 0 的虚拟站点，站点列表按位置排序后统一处理。当前位置从 0 开始，先计算相邻位置差，再扣除差值。到达终点时若仍需要补油，补油次数应计入答案；如果没有可用站点则返回 -1。
4. 给出堆实现
Python 的 heapq 是最小堆，因此把油量取负模拟最大堆。每个站点只入堆一次，每次真正补油才弹出并计数：
import heapq
def min_refuel_stops(target, start_fuel, stations):
fuel = start_fuel
previous = 0
max_heap = []
stops = 0
for position, station_fuel in [*stations, (target, 0)]:
fuel -= position - previous
while fuel < 0 and max_heap:
fuel += -heapq.heappop(max_heap)
stops += 1
if fuel < 0:
return -1
heapq.heappush(max_heap, -station_fuel)
previous = position
return stops5. 分析复杂度与测试边界
设站点数为 n。每个油量最多入堆一次、出堆一次，时间复杂度为 O(n log n)，堆空间为 O(n)。测试应覆盖初始油量足够、第一站不可达、最后一站后仍需补油、油量为 0、多个同位置站点、刚好到达终点和目标不可达。
高质量示范回答
我会把终点作为油量为 0 的虚拟站点按序扫描。扫描时先扣除行驶距离，再把已经经过的站点油量放入最大堆；当剩余油量为负时，说明必须增加一次停止，就反复取出历史上最大的油量，直到能够到达当前位置。若堆为空仍为负则返回 -1。最大堆的正确性来自交换论证：在同一次被迫停止中，用更大的已经过油量替换更小的油量不会增加停止次数，也不会减少后续可达范围。每个站点最多入堆和出堆一次，因此复杂度为 O(n log n)，空间为 O(n)。
常见错误
- 到达站点就立即加油，把最少次数题误写成固定顺序模拟。
- 只在站点之间检查，不检查从最后一站到终点的距离。
- 把当前未使用油量和堆中可选油量混为一谈。
- 用最小堆取最小油量，破坏延迟贪心的最优性。
- 忘记站点只能在到达后加入堆，提前使用未来燃油。
- 只测试可达样例，没有覆盖空堆、零油量和溢出边界。
追问及应对
为什么不能每到一个站点就选最大油量？
因为目标是停止次数。提前取油可能增加停止次数，却没有改善最终可达性；延迟到燃油不足时再取，才能让每次停止都解决真实的可达性约束。
如果每个站点可以部分加油怎么办？
题目目标和状态会改变。若燃油价格或容量也参与优化，需要重新定义成本函数；当前证明依赖一次取走整站燃油且停止次数按站点计数。
为什么同位置的多个站点不会破坏算法？
它们的距离差为 0，可以按任意顺序加入堆；只有在后续需要补油时才选择其中最大的油量，结果与同时看到这些站点相同。
如何改成返回实际停靠站点？
堆元素保存油量与站点索引。每次弹出时记录索引；最终记录的是被延迟选择的站点集合，按选择时序或位置排序即可生成路线。