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;
        }
    }
}


回到顶部