LeetcodeHard-871最低加油次数

Posted on Edited on

写在前面：该题转载至leetcode力扣 No.871–最低加油次数 😃

题目描述：

No.871最低加油次数

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

沿途有加油站，用数组 stations表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

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

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

示例1：

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

示例2：

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

示例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 升。然后开车抵达目的地。沿途在两个加油站停靠，所以返回 2 。

数据范围：

1 <= target, startFuel <= 109
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 109

默认代码模板：

C:

1
2
3
int minRefuelStops(int target, int startFuel, int** stations, int stationsSize, int* stationsColSize) {
    
}

Python3:

1
2
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:

题目解析：

dp可以，贪心也可以，这里先说dp

动态规划：

转移方程：

dp[j + 1] = max(dp[j + 1],dp[j] + stations[i][1])

dp[j]表示加了j次油的情况下最远行驶距离，如果在最新遍历到的一个加油站加油能够使行驶距离到新高的话就更新dp[]，

每次途径一个加油站都往回遍历一遍已经走过的加油站更新dp[i]，

如果目的地target<dp[i],就说明在i次加油的情况下能到目的地，在符合条件的dp[i]中选择最小的i值即为所求答案。

复杂度：

每次遍历到新的加油站都要回头看一遍遍历过的，所以时间复杂度O(n2).

要在程序中维护数组dp[],其大小是n,空间复杂度O(n).

完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minRefuelStops(int target, int startFuel, int** stations, int stationsSize, int* stationsColSize){
    long dp[stationsSize+1];
    for(int i=1;i<=stationsSize;i++)
        dp[i]=0;
    dp[0] = startFuel;//dp[i]为加i次油能到的最远距离
    for (int i = 0; i < stationsSize; i++) //途径的加油站
        for (int j = i; j >= 0; j--) //每次遍历到一个新的加油站的时候回头看能否更新dp[]
            if (dp[j] >= stations[i][0]) 
                dp[j + 1] = dp[j + 1]>dp[j] + stations[i][1]?dp[j + 1]:dp[j] + stations[i][1];//如果在当前遍历到的加油站加油，会不会跑得更远？(dp[]变得更大)
    for (int i = 0; i <= stationsSize; i++) 
        if (dp[i] >= target) //i次是能到目的地的最小的加油次数
            return i;
    return -1;
}

反悔贪心：

用一个最大堆维护当前遍历到的加油站的加油量,如果当前行驶距离小于目的地的距离，就从最大堆中取出最大值，加到行驶范围中，加油次数自增，再做距离的判断。

如果在某次判断中第一次行驶距离大于等于了目的地的距离，就返回当前的加油次数，如果堆已经空了都没到目的地就返回-1。

完整代码

这里引用了 灵茶山艾府大佬的python题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations.append((target, 0))
        ans, miles = 0, startFuel
        fuel_heap = []  # 下面把堆中元素取反，当作最大堆用
        for position, fuel in stations:
            while fuel_heap and miles < position:  # 没有足够的油到达 position
                miles -= heappop(fuel_heap)  # 选油量最多的油桶
                ans += 1
            if miles < position:  # 无法到达
                return -1
            heappush(fuel_heap, -fuel)  # 留着后面加油
        return ans

作者：灵茶山艾府
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Connect With Me

TTTTTThank You!