Skip to content

871. Minimum Number of Refueling Stops

871. Minimum Number of Refueling Stops

题目: https://leetcode.com/problems/minimum-number-of-refueling-stops/

难度: Hard

题意：

  1. 一辆车要从start跑到target，带着fuel单位的油
  2. 中间有很多个加油站，给定加油站的坐标和油量。到了加油站你可以选择到站加油和直接过站
  3. 求最少需要停几个加油站

思路：

  • 看起来是不是跟403的Frog jump很像啊，看数据范围，确实也是个动态规划的题目，动态规划的解法留给大家做，这里说一个更简单的方法
  • 我们可以换种思路。每次到站之后，把所有加油站的油都带上。先不加，等到有需要的时候再加。如果发现不够油到下个加油站，那么我们就优先选择油多的加油站的油来加，相当于我们在那个加油站停了。这里为什么优先选择油多的加油站呢？因为油多也是一站，油少也是一站。
  • 如果把所有的油加满都达不到下个加油站，那么，输出-1
  • 如果可以到target之后，我们就输出加了多少个加油站的油即可
  • 中间那部分，优先选择油多，我们需要维护一个优先队列（即最大堆），复杂度o(nlogn)，当然按照数据范围，就算是用一个链表啊，数组啊，o(n^2)照样能过，这道题的数据范围出错了，应该是stations.length<=100000
  • 这种算法叫贪心

代码：

class Solution {
    private int runTo(int start, int fuel, int target, PriorityQueue<Integer> queue) {
        fuel -= target - start;
        while (fuel < 0) {
            Integer top = queue.poll();
            if (top == null) {
                return -1;
            }
            fuel += top;
        }
        return fuel;
    }

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        int start = 0;
        int fuel = startFuel;

        for (int i = 0;i < stations.length;i++) {
            fuel = runTo(start, fuel, stations[i][0], queue);
            if (fuel == -1) {
                return fuel;
            }
            queue.add(stations[i][1]);
            start = stations[i][0];
        }

        if (runTo(start, fuel, target, queue) != -1) {
            return stations.length - queue.size();
        } else {
            return -1;
        }
    }
}
回到顶部