贪心 汽车加油 java_汽车加油问题之贪心算法

汽车加油问题是一个经典的贪心算法问题。假设有一辆汽车要从起点出发到达终点，途中有若干个加油站。汽车的油箱可以装无限多的油，但一次只能行驶一定的里程，而且在到达加油站时必须加满油。现在要求你计算最少需要加几次油才能到达终点。

贪心算法的思路是每次在当前位置选择油量最多的加油站加油，这样可以保证到达下一个加油站时汽车的油量最多，从而最大化行驶距离。当油量不足以到达下一个加油站时，就在当前位置加油。

下面是 Java 代码实现：

public static int minRefuelStops(int target, int startFuel, int[][] stations) {
    int curFuel = startFuel;
    int stops = 0;
    int i = 0;
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
    while (curFuel < target) {
        while (i < stations.length && stations[i][0] <= curFuel) {
            pq.offer(stations[i][1]);
            i++;
        }
        if (pq.isEmpty()) {
            return -1;
        }
        curFuel += pq.poll();
        stops++;
    }
    return stops;
}

其中，target 表示终点距离，startFuel 表示起始油量，stations 表示加油站的信息，每个加油站的信息包括距离起点的距离和可以加的油量。使用 PriorityQueue 存储每个加油站可以加的油量，每次选择油量最多的加油站加油。如果在某个加油站时油量不足以到达下一个加油站，则返回 -1，表示无法到达终点。