加油站的最小数量-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

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

思路：

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

代码：

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

该分类下的相关小册推荐：

算法面试通关 50 讲

数据结构与算法(下)

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法(上)

数据结构与算法之美

业务开发实用算法精讲