LeetCode 871. 最低加油次数

871. 最低加油次数

 

 【贪心+优先队列】把当前油量能到达的加油站全部加入到优先队列中，按照加油量进行排序，如果当前不能到达终点，就把队列中最大的油加上，然后继续把找加完油之后能到达的加油站加入队列，如果最后队列为空还没能达到终点就返回-1.

以样例3为：

target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 

1.最初有10，能到达的只有[10, 60]，把他加入队列。 

2.由于当前只行驶到10，还不到100，因此需要中途加油，将队列中的60拿出来加油，此时可以行驶到70，于是把后面70之前的加油站都加入队列，并按照油量排序后为：[60, 40], [20, 30], [30, 30]

3.当前行驶了70，需要继续加油，取出队列中最大的40，加完后总里程为110可到达终点。

贪心的精髓在于，在当前油量能到达的加油站中尽可能选择油量高的加油站加油。

class Solution {

    // 贪心 找能到达的加油站中加的最多的

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int sum = startFuel;
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> { return b[1] - a[1]; });
        int i = 0, n = stations.length, ans = 0;
        while (true) {
            if (sum >= target) {
                return ans;
            }
            for (; i < n; i++) {
                if (stations[i][0] <= sum) {
                    queue.offer(stations[i]);
                } else {
                    break;
                }
            }
            if (queue.isEmpty()) {
                return -1;
            }
            int[] top = queue.poll();
            sum += top[1];
            ans++;
        }
    }
}