class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
}
};
871. 最低加油次数
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的，其中最初有 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 升。然后我们开车抵达目的地。 我们沿途在1两个加油站停靠，所以返回 2 。
提示：
1 <= target, startFuel, stations[i][1] <= 10^90 <= stations.length <= 5000 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target原站题解
rust 解法, 执行用时: 1 ms, 内存消耗: 2.1 MB, 提交时间: 2024-10-07 09:15:40
use std::collections::BinaryHeap;
impl Solution {
pub fn min_refuel_stops(target: i32, start_fuel: i32, mut stations: Vec<Vec<i32>>) -> i32 {
stations.push(vec![target, 0]);
let mut ans = 0;
let mut miles = start_fuel;
let mut fuel_heap = BinaryHeap::new();
for station in stations {
let position = station[0];
while !fuel_heap.is_empty() && miles < position { // 没有足够的油到达 position
miles += fuel_heap.pop().unwrap(); // 选油量最多的油桶
ans += 1;
}
if miles < position { // 无法到达
return -1;
}
fuel_heap.push(station[1]); // 留着后面加油
}
ans
}
}
javascript 解法, 执行用时: 84 ms, 内存消耗: 54.8 MB, 提交时间: 2024-10-07 09:15:09
/**
* @param {number} target
* @param {number} startFuel
* @param {number[][]} stations
* @return {number}
*/
var minRefuelStops = function(target, startFuel, stations) {
stations.push([target, 0]);
let ans = 0, prePosition = 0, curFuel = startFuel;
const fuelHeap = new MaxPriorityQueue();
for (const [position, fuel] of stations) {
curFuel -= position - prePosition; // 每行驶 1 英里用掉 1 升汽油
while (!fuelHeap.isEmpty() && curFuel < 0) { // 没油了
curFuel += fuelHeap.dequeue().element; // 选油量最多的油桶
ans++;
}
if (curFuel < 0) { // 无法到达
return -1;
}
fuelHeap.enqueue(fuel); // 留着后面加油
prePosition = position;
}
return ans;
};
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-12 15:52:58
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
golang 解法, 执行用时: 16 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-12 15:52:39
// 贪心
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 }
javascript 解法, 执行用时: 80 ms, 内存消耗: 43.5 MB, 提交时间: 2023-06-12 15:52:09
/**
* @param {number} target
* @param {number} startFuel
* @param {number[][]} stations
* @return {number}
*/
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;
};
java 解法, 执行用时: 6 ms, 内存消耗: 42.7 MB, 提交时间: 2023-06-12 15:51:56
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;
}
}
golang 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-12 15:51:40
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
}
python3 解法, 执行用时: 772 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-12 15:51:24
# 动态规划
# dp[i] 表示加油 i 次的最大行驶英里数
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)
golang 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-12 15:50:17
func minRefuelStops(target int, startFuel int, stations [][]int) (ans int) {
pq := &IntHeap{}
for cur, idx, fuel := 0, 0, startFuel; cur < target; {
cur += fuel
for idx < len(stations) && stations[idx][0] <= cur {
heap.Push(pq, stations[idx][1])
idx++
}
if cur < target {
if pq.Len() == 0 {
return -1
}
ans++
fuel = heap.Pop(pq).(int)
}
}
return
}
type IntHeap []int
func (h IntHeap) Len() int{return len(h)}
func (h IntHeap) Less(i, j int) bool{return h[i] > h[j]}
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i]}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n - 1]
*h = old[0 : n - 1]
return x
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
java 解法, 执行用时: 3 ms, 内存消耗: 42.4 MB, 提交时间: 2023-06-12 15:49:59
class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);
int cur = 0, ans = 0;
for (int idx = 0, fuel = startFuel; cur < target; ) {
cur += fuel;
while (idx < stations.length && stations[idx][0] <= cur) {
pq.add(stations[idx++][1]);
}
if (cur < target) {
if (pq.isEmpty()) {
break;
}
ans++;
fuel = pq.poll();
}
}
return cur >= target ? ans : -1;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-12 15:49:44
'''
最大堆
每次都走当前的油的距离，将经过的加油站的油都加入最大堆中。
如果走到的距离没超过目标距离，从累计到的油中选油最多的那次加油（收益最大）。
重复以上步骤。
'''
import heapq
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
fuels = []
cur, idx, fuel, ans = 0, 0, startFuel, 0
while cur < target:
cur += fuel
while idx < len(stations) and stations[idx][0] <= cur:
heapq.heappush(fuels, -stations[idx][1])
idx += 1
if cur < target:
if not fuels:
break
else:
fuel = -heapq.heappop(fuels)
ans += 1
return ans if cur >= target else -1