871. 最低加油次数
题目描述
一辆车从位置 0 出发向东开往位置 target。车开 1 英里耗油 1 升，油箱容量无限，出发时有 startFuel 升油。
沿途的加油站由数组 stations 给出，stations[i] = [position_i, fuel_i] 表示在位置 position_i 有一个存有 fuel_i 升油的加油站，位置严格递增。车到达加油站时可以选择停下，把该站的油全部加进油箱。
到达加油站或终点时油量恰好为 0 也算到达，此时仍可以在该站加油。
返回到达 target 所需的最少加油次数。如果无论如何都到不了，返回 -1。
示例 1
输入：target = 1, startFuel = 1, stations = [] 输出：0
解释：初始油量正好够开到终点，无需加油。
示例 2
输入：target = 100, startFuel = 1, stations = [[10,100]] 输出：-1
解释：1 升油连位置 10 的加油站都到不了。
示例 3
输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 输出：2
解释：在位置 10 加 60 升，再在位置 60 加 40 升，即可到达终点，共 2 次。
数据范围
1 <= target, startFuel <= 10^90 <= stations.length <= 5001 <= position_i < position_{i+1} < target1 <= fuel_i < 10^9
解题思路：动态规划（加油 t 次能到达的最远距离）
设 dp[t] 为加油 t 次最远能开到的位置（也就是起始油 + 加过的油）。按位置逐个考虑加油站 i：如果 dp[t] >= pos，说明加 t 次油能开到这里，再在这里加油就能开到 dp[t] + fuel，用它更新 dp[t+1]。和 0-1 背包一样，t 要从大到小枚举，保证每个加油站只用一次。最后找最小的 t 使 dp[t] >= target。
为什么正确
处理完前 i 个加油站后，dp[t] = 只在前 i 个站里选 t 个加油时，能开到的最远位置。
复杂度分析
时间 O(n²)，空间 O(n)。用大根堆的贪心解法可做到 O(n log n)。
易错点
t 必须从大到小枚举：如果从小到大，dp[t+1] 刚用当前站更新完，又会被用来更新 dp[t+2]，等于在同一个站加了两次油。另外距离可达 5·10^11，C++/Java 需要 long。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
n = len(stations)
dp = [startFuel] + [0] * n
for i in range(n):
pos, fuel = stations[i]
for t in range(i, -1, -1):
if dp[t] >= pos:
dp[t + 1] = max(dp[t + 1], dp[t] + fuel)
for t in range(n + 1):
if dp[t] >= target:
return t
return -1class 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++) {
long pos = stations[i][0], fuel = stations[i][1];
for (int t = i; t >= 0; t--) {
if (dp[t] >= pos) {
dp[t + 1] = Math.max(dp[t + 1], dp[t] + fuel);
}
}
}
for (int t = 0; t <= n; t++) {
if (dp[t] >= target) {
return t;
}
}
return -1;
}
}class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
int n = stations.size();
vector<long long> dp(n + 1, 0); dp[0] = startFuel;
for (int i = 0; i < n; i++) {
long long pos = stations[i][0], fuel = stations[i][1];
for (int t = i; t >= 0; t--) {
if (dp[t] >= pos) {
dp[t + 1] = max(dp[t + 1], dp[t] + fuel);
}
}
}
for (int t = 0; t <= n; t++) {
if (dp[t] >= target) {
return t;
}
}
return -1;
}
};func minRefuelStops(target int, startFuel int, stations [][]int) int {
n := len(stations)
dp := make([]int, n+1); dp[0] = startFuel
for i := 0; i < n; i++ {
pos, fuel := stations[i][0], stations[i][1]
for t := i; t >= 0; t-- {
if dp[t] >= pos {
dp[t+1] = max(dp[t+1], dp[t]+fuel)
}
}
}
for t := 0; t <= n; t++ {
if dp[t] >= target {
return t
}
}
return -1
}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++) {
const [pos, fuel] = stations[i];
for (let t = i; t >= 0; t--) {
if (dp[t] >= pos) {
dp[t + 1] = Math.max(dp[t + 1], dp[t] + fuel);
}
}
}
for (let t = 0; t <= n; t++) {
if (dp[t] >= target) {
return t;
}
}
return -1;
};function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
const n = stations.length;
const dp = new Array(n + 1).fill(0); dp[0] = startFuel;
for (let i = 0; i < n; i++) {
const [pos, fuel] = stations[i];
for (let t = i; t >= 0; t--) {
if (dp[t] >= pos) {
dp[t + 1] = Math.max(dp[t + 1], dp[t] + fuel);
}
}
}
for (let t = 0; t <= n; t++) {
if (dp[t] >= target) {
return t;
}
}
return -1;
}其他解法
DP 枚举加油次数，正确性显然但是 O(n²)；大根堆贪心把加油决策推迟到油不够时，只需 O(n log n)。
解法 2：贪心 + 大根堆（事后补加） 时间 O(n log n)，空间 O(n)
把加油看成“经过加油站时先把油存起来，等油不够时再决定用哪一站”。用 fuel 表示当前能到达的最远位置，把所有位置 ≤ fuel 的加油站油量放进大根堆。只要 fuel < target，就从堆中取出最大的油量加上并把次数加 1；堆空了还到不了就返回 -1。
每次都补最大的油量，交换论证可证明最优，复杂度降到 O(n log n)。“先记下来、需要时再反悔式使用”的思路比 DP 更跳跃，正确性不如 DP 直观。
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
heap = []
fuel = startFuel
i = ans = 0
while fuel < target:
while i < len(stations) and stations[i][0] <= fuel:
heapq.heappush(heap, -stations[i][1])
i += 1
if not heap:
return -1
fuel -= heapq.heappop(heap)
ans += 1
return ansclass Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
long fuel = startFuel;
int i = 0, ans = 0, n = stations.length;
while (fuel < target) {
while (i < n && stations[i][0] <= fuel) pq.offer(stations[i++][1]);
if (pq.isEmpty()) return -1;
fuel += pq.poll();
ans++;
}
return ans;
}
}class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
priority_queue<int> pq;
long long fuel = startFuel;
int i = 0, ans = 0, n = stations.size();
while (fuel < target) {
while (i < n && stations[i][0] <= fuel) pq.push(stations[i++][1]);
if (pq.empty()) return -1;
fuel += pq.top();
pq.pop();
ans++;
}
return ans;
}
};type fuelHeap []int
func (h fuelHeap) Len() int { return len(h) }
func (h fuelHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h fuelHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *fuelHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *fuelHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func minRefuelStops(target int, startFuel int, stations [][]int) int {
h := &fuelHeap{}
fuel, i, ans := startFuel, 0, 0
for fuel < target {
for i < len(stations) && stations[i][0] <= fuel {
heap.Push(h, stations[i][1])
i++
}
if h.Len() == 0 {
return -1
}
fuel += heap.Pop(h).(int)
ans++
}
return ans
}var minRefuelStops = function(target, startFuel, stations) {
const heap = [];
const push = (v) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] >= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
let s = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < heap.length && heap[l] > heap[s]) s = l;
if (r < heap.length && heap[r] > heap[s]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
};
let fuel = startFuel, i = 0, ans = 0;
while (fuel < target) {
while (i < stations.length && stations[i][0] <= fuel) push(stations[i++][1]);
if (heap.length === 0) return -1;
fuel += pop();
ans++;
}
return ans;
};function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
const heap: number[] = [];
const push = (v: number): void => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] >= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = (): number => {
const top = heap[0], last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
let s = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < heap.length && heap[l] > heap[s]) s = l;
if (r < heap.length && heap[r] > heap[s]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
};
let fuel = startFuel, i = 0, ans = 0;
while (fuel < target) {
while (i < stations.length && stations[i][0] <= fuel) push(stations[i++][1]);
if (heap.length === 0) return -1;
fuel += pop();
ans++;
}
return ans;
}