0871-最低加油次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

汽车从起点出发驶向目的地，该目的地位于出发位置东面 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

方法一：动态规划

由于数组 stations 按照加油站的位置非递减排序，因此从左到右遍历数组 stations 的过程中，当遍历到一个加油站时，位置小于该加油站的所有加油站都已经被遍历过。

用 n 表示数组 stations 的长度，即加油站的个数。最多可以加油 n 次，为了得到可以到达目的地的最少加油次数，需要计算每个加油次数对应的最大行驶英里数，然后得到最大行驶英里数大于等于 target 的最少加油次数。

用 dp}[i] 表示加油 i 次的最大行驶英里数。由于初始时汽油量是 startFuel 升，可以行驶 startFuel 英里，因此 dp}[0] = \textit{startFuel。

当遍历到加油站 stations}[i] 时，假设在到达该加油站之前已经加油 j 次，其中 0 \le j \le i，则只有当 dp}[j] \ge \textit{stations}[i][0] 时才能在加油 j 次的情况下到达加油站 stations}[i] 的位置，在加油站 stations}[i] 加油之后，共加油 j + 1 次，可以行驶的英里数是 dp}[j] + \textit{stations}[i][1]。遍历满足 0 \le j \le i 且 dp}[j] \ge \textit{stations}[i][0] 的每个下标 j，计算 dp}[j + 1] 的最大值。

当遍历到加油站 stations}[i] 时，对于每个符合要求的下标 j，计算 dp}[j + 1] 时都是将加油站 stations}[i] 作为最后一次加油的加油站。为了确保每个 dp}[j + 1] 的计算中，加油站 stations}[i] 只会被计算一次，应该按照从大到小的顺序遍历下标 j。

以示例 3 为例。对于加油站 stations}[2] 计算之后，dp}[2] = 100。对于加油站 stations}[3] 计算的过程中会将 dp}[2] 的值更新为 110，如果在计算 dp}[3] 之前计算 dp}[2]，则 dp}[3] 的值将被错误地计算为 dp}[2] + \textit{stations}[3][1] = 150。只有当从大到小遍历下标 j 时，才能得到 dp}[3] = 140 的正确结果。

当所有的加油站遍历结束之后，遍历 dp，寻找使得 dp}[i] \ge \textit{target 的最小下标 i 并返回。如果不存在这样的下标，则无法到达目的地，返回 -1。

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        dp = [startFuel] + [0] * len(stations)
        for i, (pos, fuel) in enumerate(stations):
            for j in range(i, -1, -1):
                if dp[j] >= pos:
                    dp[j + 1] = max(dp[j + 1], dp[j] + fuel)
        return next((i for i, v in enumerate(dp) if v >= target), -1)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        long[] dp = new long[n + 1];
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int MinRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.Length;
        long[] dp = new long[n + 1];
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = Math.Max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size();
        vector<long> dp(n + 1);
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] >= stations[i][0]) {
                    dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int minRefuelStops(int target, int startFuel, int** stations, int stationsSize, int* stationsColSize){
    long *dp = (long *)malloc(sizeof(long) * (stationsSize + 1));
    memset(dp, 0, sizeof(long) * (stationsSize + 1));
    dp[0] = startFuel;
    for (int i = 0; i < stationsSize; i++) {
        for (int j = i; j >= 0; j--) {
            if (dp[j] >= stations[i][0]) {
                dp[j + 1] = MAX(dp[j + 1], dp[j] + stations[i][1]);
            }
        }
    }
    for (int i = 0; i <= stationsSize; i++) {
        if (dp[i] >= target) {
            free(dp);
            return i;
        }
    }
    free(dp);
    return -1;
}
[sol1-Golang]
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
func minRefuelStops(target, startFuel int, stations [][]int) int {
    n := len(stations)
    dp := make([]int, n+1)
    dp[0] = startFuel
    for i, s := range stations {
        for j := i; j >= 0; j-- {
            if dp[j] >= s[0] {
                dp[j+1] = max(dp[j+1], dp[j]+s[1])
            }
        }
    }
    for i, v := range dp {
        if v >= target {
            return i
        }
    }
    return -1
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var minRefuelStops = function(target, startFuel, stations) {
    const n = stations.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = startFuel;
    for (let i = 0; i < n; i++) {
        for (let j = i; j >= 0; j--) {
            if (dp[j] >= stations[i][0]) {
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
            }
        }
    }
    for (let i = 0; i <= n; i++) {
        if (dp[i] >= target) {
            return i;
        }
    }
    return -1;
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是数组 stations 的长度。动态规划的状态数是 O(n)，每个状态需要 O(n) 的时间计算，因此时间复杂度是 O(n^2)。

  • 空间复杂度：O(n)，其中 n 是数组 stations 的长度。需要创建长度为 n + 1 的数组 dp。

方法二：贪心

用 n 表示数组 stations 的长度，即加油站的个数。行驶的过程中依次到达 n + 1 个位置，分别是 n 个加油站和目的地。为了得到最少加油次数，应该在确保每个位置都能到达的前提下，选择最大加油量的加油站加油。

为了得到已经到达过的加油站中的最大加油量，需要使用优先队列记录所有已经到达过的加油站的加油量，优先队列中的最大元素位于队首，即每次从优先队列中取出的元素都是优先队列中的最大元素。

从左到右遍历数组 stations，对于每个加油站，首先判断该位置是否可以达到，然后将当前加油站的加油量添加到优先队列中。对于目的地，则只需要判断是否可以达到。

具体做法如下。

  1. 计算当前位置（加油站或目的地）与上一个位置的距离之差，根据该距离之差得到从上一个位置行驶到当前位置需要使用的汽油量，将使用的汽油量从剩余的汽油量中减去。

  2. 如果剩余的汽油量小于 0，则表示在不加油的情况下无法从上一个位置行驶到当前位置，需要加油。取出优先队列中的最大元素加到剩余的汽油量，并将加油次数加 1，重复该操作直到剩余的汽油量大于等于 0 或优先队列变为空。

  3. 如果优先队列变为空时，剩余的汽油量仍小于 0，则表示在所有经过的加油站加油之后仍然无法到达当前位置，返回 -1。

  4. 如果当前位置是加油站，则将当前加油站的加油量添加到优先队列中，并使用当前位置更新上一个位置。

如果无法到达目的地，则在遍历过程中返回 -1。如果遍历结束仍未返回 -1，则可以到达目的地，返回加油次数。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)
        ans, fuel, prev, h = 0, startFuel, 0, []
        for i in range(n + 1):
            curr = stations[i][0] if i < n else target
            fuel -= curr - prev
            while fuel < 0 and h:
                fuel -= heappop(h)
                ans += 1
            if fuel < 0:
                return -1
            if i < n:
                heappush(h, -stations[i][1])
                prev = curr
        return ans
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        int ans = 0, prev = 0, fuel = startFuel;
        int n = stations.length;
        for (int i = 0; i <= n; i++) {
            int curr = i < n ? stations[i][0] : target;
            fuel -= curr - prev;
            while (fuel < 0 && !pq.isEmpty()) {
                fuel += pq.poll();
                ans++;
            }
            if (fuel < 0) {
                return -1;
            }
            if (i < n) {
                pq.offer(stations[i][1]);
                prev = curr;
            }
        }
        return ans;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int MinRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        int ans = 0, prev = 0, fuel = startFuel;
        int n = stations.Length;
        for (int i = 0; i <= n; i++) {
            int curr = i < n ? stations[i][0] : target;
            fuel -= curr - prev;
            while (fuel < 0 && pq.Count > 0) {
                fuel += pq.Dequeue();
                ans++;
            }
            if (fuel < 0) {
                return -1;
            }
            if (i < n) {
                pq.Enqueue(stations[i][1], -stations[i][1]);
                prev = curr;
            }
        }
        return ans;
    }
}
[sol2-C++]
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 {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> pq;
        int ans = 0, prev = 0, fuel = startFuel;
        int n = stations.size();
        for (int i = 0; i <= n; i++) {
            int curr = i < n ? stations[i][0] : target;
            fuel -= curr - prev;
            while (fuel < 0 && !pq.empty()) {
                fuel += pq.top();
                pq.pop();
                ans++;
            }
            if (fuel < 0) {
                return -1;
            }
            if (i < n) {
                pq.emplace(stations[i][1]);
                prev = curr;
            }
        }
        return ans;
    }
};
[sol2-Golang]
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
26
27
func minRefuelStops(target, startFuel int, stations [][]int) (ans int) {
    fuel, prev, h := startFuel, 0, hp{}
    for i, n := 0, len(stations); i <= n; i++ {
        curr := target
        if i < n {
            curr = stations[i][0]
        }
        fuel -= curr - prev
        for fuel < 0 && h.Len() > 0 {
            fuel += heap.Pop(&h).(int)
            ans++
        }
        if fuel < 0 {
            return -1
        }
        if i < n {
            heap.Push(&h, stations[i][1])
            prev = curr
        }
    }
    return
}

type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 stations 的长度。需要遍历数组 stations 一次，每个加油站的汽油量最多添加到优先队列和从优先队列中移除各一次，每次优先队列的操作需要 O(\log n) 的时间，因此时间复杂度是 O(n \log n)。

  • 空间复杂度：O(n)，其中 n 是数组 stations 的长度。优先队列需要 O(n) 的空间。

 Comments
On this page
0871-最低加油次数