先把问题的核心信息梳理清楚：

定义与输入 #

给定的加油站类代码如下：

class GasStation { 
    int distanceToDestination; 
    int availableGas; 
}

我们需要处理三个关键参数：

• g：车辆初始油量（单位：加仑）
• d：到目的地的总距离（单位：英里）
• gasStations：加油站列表，每个站包含两个属性：
  • distanceToDestination：该站到目的地的距离
  • availableGas：该站能为车辆添加的油量

补充规则：车辆无油量容量限制，默认每行驶1英里消耗1加仑汽油（这是题目隐含的必要前提，否则无法进行油量与距离的换算）。

示例输入：

g = 10 gallon, d = 20 miles, gasStations = [[15, 1], [14,10], [12,12]]

解题思路：贪心算法 #

要实现最少停靠次数，核心逻辑是每次在当前油量能覆盖的范围内，优先选能提供最多油量的加油站停靠——这样能最大化后续的行驶距离，从根源上减少停靠次数。具体步骤如下：

1. 预处理加油站列表

   • 把每个加油站的distanceToDestination转换为离出发点的距离：distanceFromStart = d - station.distanceToDestination
   • 过滤掉已经在目的地之后的站（即distanceToDestination <= 0，因为已经到终点，无需停靠）
   • 按distanceFromStart从小到大排序，确保我们能按照行驶顺序遍历加油站

2. 模拟行驶过程

   • 初始化变量：
     • currentGas = g：当前剩余油量
     • currentPosition = 0：当前所在位置
     • stopCount = 0：已停靠次数
     • 一个最大堆（优先队列）：用来存储当前能到达范围内的所有加油站的可用油量，方便快速取出油量最多的站
   • 遍历排序后的加油站，同时处理到达目的地的逻辑：
     1. 先检查当前油量能否到达下一个加油站：计算从当前位置到下一个站的距离needed = nextStation.distanceFromStart - currentPosition
     2. 如果当前油量不够，就从最大堆里取出油量最多的站，给车辆加油，停靠次数加1，直到油量足够到达下一个站；如果堆为空但还是不够油，说明无法到达目的地，返回-1
     3. 行驶到下一个站，消耗对应油量（currentGas -= needed），把该站的可用油量加入最大堆，更新当前位置为该站的位置
   • 最后检查能否到达目的地：计算从当前位置到目的地的距离needed = d - currentPosition，如果当前油量不够，继续从堆里取油加油，直到油量足够或堆为空。如果最终能到达，返回stopCount，否则返回-1

示例验证 #

我们用给定的示例走一遍完整流程：

1. 预处理加油站：
   • 各站离出发点的距离分别是：20-15=5、20-14=6、20-12=8
   • 排序后顺序：[5,1]、[6,10]、[8,12]
2. 模拟行驶：
   • 初始状态：currentGas=10，currentPosition=0，stopCount=0，最大堆为空
   • 当前油量能覆盖的范围是0~10英里，把这三个站的油量（1、10、12）加入堆，堆顶是12
   • 现在要到达目的地还需要20英里，当前只能走到10英里，油量不够。从堆里取出最大的12（对应8英里的站）：
     • 行驶到8英里站，消耗8加仑，currentGas=10-8=2
     • 加12加仑，currentGas=14，stopCount=1，currentPosition=8
   • 现在当前油量能走到8+14=22英里，已经超过目的地20英里，直接开到终点即可

最终最少停靠次数是1次。

内容的提问来源于stack exchange，提问作者zonyang