LeetCode 871. 最低加油次数

1. 问题描述：

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [position, fuel] 表示第 i 个加油站位于出发位置东面 position 英里处，并且有 fuel 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

（注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。）

示例 1：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

提示：

• 1 <= target, startFuel <= 10^9
• 0 <= stations.length <= 500
• 1 <= positioni < positioni+1 < target
• 1 <= fueli < 10^9

2. 代码分析：

本题也是一道很好的考查动态规划或贪心的题目。
二维动态规划，背包+贪心，到达每一站可以选择加或不加油，并更新到达该站且加了某数量次油的最大可行里程。

3. 代码

package suanfa;

import java.util.PriorityQueue;

class MinRefuelStopsSolution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if (startFuel >= target) return 0;
        int n = stations.length, prev = 0;
        int fuel = startFuel, ans = 0;
        PriorityQueue<Integer> p = new PriorityQueue<>((a, b) -> (b - a));
        for (int i = 0; i < n; ++i) {
            int cost = stations[i][0] - prev;
            fuel -= cost;
            while (fuel < 0 && !p.isEmpty()) {
                fuel += p.poll();
                ans++;
            }
            if (fuel < 0) return -1;
            p.offer(stations[i][1]);
            prev = stations[i][0];
        }
        fuel -= (target - prev);
        while (fuel < 0 && !p.isEmpty()) {
            fuel += p.poll();
            ans++;
        }
        if (fuel < 0) return -1;
        return ans;
    }

    public static void main(String[] args) {
        MinRefuelStopsSolution solution = new MinRefuelStopsSolution();
        int target = 100;
        int startFuel = 10;
        int[][] stations = {{10, 60}, {20, 30}, {30, 30}, {60, 40}};
        int result = solution.minRefuelStops(target, startFuel, stations);
        System.out.println("最低加油次数: " + result);
    }
}