[LeetCode解题报告] 871. 最低加油次数

一、 题目

1. 题目描述

871. 最低加油次数

难度：困难

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

沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

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

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

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目的地。

1
2
3
4

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：我们无法抵达目的地，甚至无法到达第一个加油站。

1
2
3
4

示例 3：

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

1
2
3
4
5
6
7
8
9

提示：

1. 1 <= target, startFuel, stations[i][1] <= 10^9
2. 0 <= stations.length <= 500
3. 0 < stations[0][0] < stations[1][0] < … < stations[stations.length-1][0] < target

2. 原题链接

链接: 871. 最低加油次数

二、 解题报告

1. 思路分析

 本题可以用dp或者贪心优先队列来解。
1

1. dp:

   • 令dp[i]为只加i次油能到达的最远地方。
   • 显然dp[i+1]能到的最远地方是dp[i]这个位置之前的所有加油站中找一个剩余的、容量最多的加油站来使用。
   • 那么我们状态转移时，只需要把用掉的站变0即可。
   • dp[i] = dp[i-1] + max{fuel[j] | pos[j]<=dp[i-1]}。注意清空之前用过的站的容量。

2. 贪心优先队列:

   • 先把加油站按位置排序，我们假设途径每个加油站都不加油，用大根堆储存途径的每个加油站容量。
   • 当我们遍历一个加油站时，发现之前加过的油到不了本站，那么应该试图从之前途径的、未使用的加油站寻找站来加油。
   • 这时的最优策略一定是找容量最大的加油站，使得我们加油次数尽可能小。
   • 那么这个数据结构就是优先队列，同时我们可能需要加多次才能到达本站点，需要while。
   • 如果队列空了，还到不了，那么显然不可能到本站，返回-1即可。
   • 特别的，加油站都遍历完了，还没到target，那么需要用target继续处理优先队列。
     

2. 复杂度分析

• dp:O(n²)
• 优先队列：O(nlog₂n)

3. 代码实现

dp。

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        stations.sort(key=lambda x:x[0])
        n = len(stations)
        dp = [0] * (n+1)  # dp[i]为加油i次最多走多远
        dp[0] = startFuel
        
        for i in range(1,n+1):
            t = -1
            for j in range(n): # 找出上次能到范围内油最多的那个加油站
                if stations[j][0] > dp[i-1] :
                    break
                if stations[j][1] <=0 :
                    continue
                if t == -1 or stations[j][1] > stations[t][1]:
                    t = j
            # print(dp,t)
            if t > -1:
                dp[i] = dp[i-1] + stations[t][1]
                if dp[i] >= target:
                    return i
                stations[t][1] = 0
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

贪心+优先队列。

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        if startFuel >= target:
            return 0
        stations.sort(key=lambda x:x[0])
        n = len(stations)
        q = []  # 储存已经经过的，没加油的加油站
        s = startFuel
        cnt = 0
        for pos,a in stations:
            while q and s < pos:  # 如果到不了，从之前经过的加油站选一个最多的加，直到能到
                s -= heapq.heappop(q)
                cnt += 1
                if s >= target:  # 加完这个发现到目标了
                    return cnt
            if s < pos:  # 都加完了还到不了
                return -1
            heapq.heappush(q,-a)  # 途经本站
        # print(q,s,cnt)
        while q and s < target:  # 经过所有加油站后，如果还没到终点，需要继续判断
            s -= heapq.heappop(q)
            cnt += 1
            if s >= target:  # 加完这个发现到目标了
                return cnt
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

三、 本题小结

1. 还是不熟练，看了题解才做出来。

四、 参考链接

• 附昨晚做的一道类似题目: [LeetCode解题报告] 630. 课程表 III