递归、动态规划、优先队列（大顶堆 / 大根堆 / 最大堆），3 方法求解《871. 最低加油次数》
例题
871. 最低加油次数
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。
示例 1：
输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目的地。
答案
递归
var minRefuelStops = function(target, startFuel, stations) {
const n = stations.length
let r = Number.MAX_SAFE_INTEGER
const d = (remainTarget, remainFuel, prev, index, count) => {
if (index === n) {
if (remainTarget <= remainFuel) r = Math.min(r, count)
return
}
const [cur, fuel] = stations[index]
if (remainFuel < cur - prev) return
d(target - cur, remainFuel + fuel - cur + prev, cur, index + 1, count + 1)
d(target - cur, remainFuel - cur + prev, cur, index + 1, count)
}
d(target, startFuel, 0, 0, 0)
return r === Number.MAX_SAFE_INTEGER ? -1 : r
};class Solution {
private int n;
private int total;
private int[][] sts;
private int r = Integer.MAX_VALUE;
public int minRefuelStops(int target, int startFuel, int[][] stations) {
n = stations.length;
total = target;
sts = stations;
d(startFuel, 0, 0, 0);
return r == Integer.MAX_VALUE ? -1 : r;
}
public void d(int remainFuel, int prev, int index, int count) {
if (index == n) {
if (remainFuel >= total - prev) r = Math.min(r, count);
return;
}
int cur = sts[index][0], fuel = sts[index][1];
if (remainFuel < cur - prev) return;
d(remainFuel + fuel - cur + prev, cur, index + 1, count + 1);
d(remainFuel - cur + prev, cur, index + 1, count);
}
}动态规划
var minRefuelStops = function(target, startFuel, stations) {
const n = stations.length
const dp = new Uint32Array(n + 1)
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 < dp.length; i++) {
if (dp[i] >= target) return i
}
return -1
};function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
const n = stations.length, 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 < dp.length; i++)
if (dp[i] >= target) return i
return -1
};class Solution {
function minRefuelStops($target, $startFuel, $stations) {
$n = count($stations);
$dp = array_fill(0, $n + 1, 0);
$dp[0] = $startFuel;
for ($i = 0; $i < $n; $i++) {
for ($j = $i; $j >= 0; $j--) {
if ($dp[$j] >= $stations[$i][0]) $dp[$j + 1] = max($dp[$j + 1], $dp[$j] + $stations[$i][1]);
}
}
foreach ($dp as $i => $v) {
if ($v >= $target) return $i;
}
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++ {
for j := i; j >= 0; j-- {
if dp[j] >= stations[i][0] {
dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])
}
}
}
for i, v := range dp {
if v >= target {
return i
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
n = len(stations)
dp = [0] * (n + 1)
dp[0] = startFuel
for i in range(0, n):
for j in range(i, -1, -1):
if dp[j] >= stations[i][0]: dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])
for i in range(0, n + 1):
if dp[i] >= target: return i
return -1 class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int n = stations.length;
int[] dp = new int[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;
}
}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));
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;
}class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
int n = stations.size();
vector<long> dp(n + 1, 0);
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;
}
};public class Solution {
public int MinRefuelStops(int target, int startFuel, int[][] stations) {
int n = stations.Length;
int[] dp = new int[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 < dp.Length; i++) {
if (dp[i] >= target) return i;
}
return -1;
}
}优先队列
var minRefuelStops = function(target, startFuel, stations) {
const n = stations.length, q = new PriorityQueue([], (a, b) => b - a)
let remainFuel = startFuel, r = 0
for (let i = 0; i <= n; i++) {
const cur = i < n ? stations[i][0] : target
while (cur > remainFuel && q.isEmpty() === false) {
remainFuel += q.pop()
r++
}
if (cur > remainFuel) return -1
if (i < n) q.push(stations[i][1])
}
return r
};
class PriorityQueue {
constructor (ar = [], compare = (a, b) => a - b) {
this.heap = []
this.size = 0
this.compare = compare
while (ar.length) this.push(ar.pop())
}
swap (a, b) {
const t = this.heap[a]
this.heap[a] = this.heap[b]
this.heap[b] = t
}
getLeftIndex(index) {
return (index << 1) + 1
}
getRightIndex(index) {
return (index << 1) + 2
}
getParentIndex(index) {
return index - 1 >> 1
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
this.swap(index, leftIndex)
this.shiftDown(leftIndex)
}
if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
this.swap(index, rightIndex)
this.shiftDown(rightIndex)
}
}
shiftUp(index) {
const parentIndex = this.getParentIndex(index)
if (parentIndex >= 0 && this.compare(this.heap[parentIndex], this.heap[index]) > 0) {
this.swap(parentIndex, index)
this.shiftUp(parentIndex)
}
}
push(v) {
this.heap.push(v)
this.shiftUp(this.size++)
}
top() {
return this.heap[0]
}
pop() {
if (this.size === 0) return null
if (--this.size === 0) return this.heap.pop()
const top = this.top()
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
isEmpty() {
return this.size === 0
}
}function minRefuelStops(target: number, startFuel: number, stations: number[][]): number {
const q = new PriorityQueue([], (a: number, b: number): number => b - a), n = stations.length
let remainFuel = startFuel, r = 0
for (let i = 0; i <= n; i++) {
const cur = i < n ? stations[i][0] : target
while (cur > remainFuel && q.isEmpty() === false) {
remainFuel += q.pop()
r++
}
if (cur > remainFuel) return -1
if (i < n) q.push(stations[i][1])
}
return r
};
class PriorityQueue {
heap: number[] = []
size: number = 0
compare: (a: number, b: number) => number
constructor(ar: number[] = [], compare = (a: number, b: number): number => a - b) {
this.heap = []
this.size = 0
this.compare = compare
while (ar.length) this.push(ar.pop())
}
swap(a: number, b: number) {
const t: number = this.heap[a]
this.heap[a] = this.heap[b]
this.heap[b] = t
}
getLeftIndex(index: number): number {
return (index << 1) + 1
}
getRightIndex(index: number): number {
return (index << 1) + 2
}
getParentIndex(index: number): number {
return index - 1 >> 1
}
shiftDown(index: number) {
const leftIndex: number = this.getLeftIndex(index)
const rightIndex: number = this.getRightIndex(index)
if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
this.swap(index, leftIndex)
this.shiftDown(leftIndex)
}
if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
this.swap(index, rightIndex)
this.shiftDown(rightIndex)
}
}
shiftUp(index: number) {
const parentIndex: number = this.getParentIndex(index)
if (parentIndex >= 0 && this.compare(this.heap[parentIndex], this.heap[index]) > 0) {
this.swap(parentIndex, index)
this.shiftUp(parentIndex)
}
}
push(value: number) {
this.heap.push(value)
this.shiftUp(this.size++)
}
top(): number {
return this.heap[0]
}
pop(): number | null {
if (this.size === 0) return null
if (--this.size === 0) return this.heap.pop()
const top = this.top()
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
isEmpty(): boolean {
return this.size === 0
}
}class Solution {
function minRefuelStops($target, $startFuel, $stations) {
$q = new PriorityQueue();
$q->setExtractFlags(SplPriorityQueue::EXTR_DATA);
$n = count($stations);
$remainFuel = $startFuel;
$r = 0;
for ($i = 0; $i <= $n; $i++) {
$cur = $i < $n ? $stations[$i][0] : $target;
while ($cur > $remainFuel && $q->isEmpty() === false) {
$remainFuel += $q->extract();
$r++;
}
if ($cur > $remainFuel) return -1;
if ($i < $n) $q->insert($stations[$i][1], $stations[$i][1]);
}
return $r;
}
}
class PriorityQueue extends SplPriorityQueue {
public function compare($priority1, $priority2) {
return $priority1 - $priority2;
}
}func minRefuelStops(target int, startFuel int, stations [][]int) int {
n, remainFuel, q, r := len(stations), startFuel, &PriorityQueue{
Compare: func(a, b int) int {
return b - a
},
}, 0
for i, cur := 0, 0; i <= n; i++ {
if i < n {
cur = stations[i][0]
} else {
cur = target
}
for cur > remainFuel && q.IsEmpty() == false {
remainFuel += q.Pop()
r++
}
if cur > remainFuel {
return -1
}
if i < n {
q.Push(stations[i][1])
}
}
return r
}
type PriorityQueue struct {
heap []int
size int
Compare func(a, b int) int
}
func (q *PriorityQueue) Swap(a, b int) {
q.heap[a], q.heap[b] = q.heap[b], q.heap[a]
}
func (q *PriorityQueue) GetLeftIndex(index int) int {
return index << 1 + 1
}
func (q *PriorityQueue) GetRightIndex(index int) int {
return index << 1 + 2
}
func (q *PriorityQueue) GetParentIndex(index int) int {
return (index - 1) >> 1
}
func (q *PriorityQueue) ShiftDown(index int) {
leftIndex, rightIndex := q.GetLeftIndex(index), q.GetRightIndex(index)
if leftIndex < q.size && q.Compare(q.heap[index], q.heap[leftIndex]) > 0 {
q.Swap(index, leftIndex)
q.ShiftDown(leftIndex)
}
if rightIndex < q.size && q.Compare(q.heap[index], q.heap[rightIndex]) > 0 {
q.Swap(index, rightIndex)
q.ShiftDown(rightIndex)
}
}
func (q *PriorityQueue) ShiftUp(index int) {
parentIndex := q.GetParentIndex(index)
if parentIndex >= 0 && q.Compare(q.heap[parentIndex], q.heap[index]) > 0 {
q.Swap(parentIndex, index)
q.ShiftUp(parentIndex)
}
}
func (q *PriorityQueue) Push(v int) {
q.heap = append(q.heap, v)
q.ShiftUp(q.size)
q.size++
}
func (q *PriorityQueue) Top() int {
return q.heap[0]
}
func (q *PriorityQueue) HeapPop() int {
n := len(q.heap)
last := q.heap[n - 1]
q.heap = q.heap[:n - 1]
return last
}
func (q *PriorityQueue) Pop() int {
if q.size == 0 {
return -1
}
q.size--
if q.size == 0 {
return q.HeapPop()
}
top := q.Top()
q.heap[0] = q.HeapPop()
q.ShiftDown(0)
return top
}
func (q *PriorityQueue) IsEmpty() bool {
return q.size == 0
}class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
n, q, remainFuel, r = len(stations), [], startFuel, 0
for i in range(0, n + 1):
cur = stations[i][0] if i < n else target
while cur > remainFuel and len(q) > 0:
remainFuel += -heappop(q)
r += 1
if cur > remainFuel: return -1
if i < n: heappush(q, -stations[i][1])
return rclass Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b- a);
int remainFuel = startFuel, n = stations.length, r = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? stations[i][0] : target;
while (cur > remainFuel && q.isEmpty() == false) {
remainFuel += q.poll();
r++;
}
if (cur > remainFuel) return -1;
if (i < n) q.offer(stations[i][1]);
}
return r;
}
}优先队列
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
priority_queue<int> q;
int remainFuel = startFuel, n = stations.size(), r = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? stations[i][0] : target;
while (cur > remainFuel && q.empty() == false) {
remainFuel += q.top();
q.pop();
r++;
}
if (cur > remainFuel) return -1;
if (i < n) q.push(stations[i][1]);
}
return r;
}
};public class Solution {
public int MinRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<int, int> q = new PriorityQueue<int, int>();
int n = stations.Length, remainFuel = startFuel, r = 0;
for (int i = 0; i <= n; i++) {
int cur = i < n ? stations[i][0] : target;
while (cur > remainFuel && q.Count > 0) {
remainFuel += q.Dequeue();
r++;
}
if (cur > remainFuel) return -1;
if (i < n) q.Enqueue(stations[i][1], -stations[i][1]);
}
return r;
}
}
