LeetCode 871. 最低加油次数

Categories:

题目描述
思路分析
1. 解法一：贪心 + 最大堆（推荐）
相似题目

题目描述

✅ 871. 最低加油次数

思路分析

解法一：贪心 + 最大堆（推荐）

核心思路：

沿途行驶时把可达加油站的油量压入最大堆。

当燃料不足以到达下一个位置时，从堆中取最大油量补充。

若堆为空仍无法前进，则返回 -1。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示加油站数量。

空间复杂度：O(n)。

import java.util.PriorityQueue;

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        int fuel = startFuel;
        int idx = 0;
        int stops = 0;

        while (fuel < target) {
            while (idx < stations.length && stations[idx][0] <= fuel) {
                maxHeap.offer(stations[idx][1]);
                idx++;
            }

            if (maxHeap.isEmpty()) {
                return -1;
            }

            fuel += maxHeap.poll();
            stops++;
        }

        return stops;
    }
}

import "container/heap"

type MaxHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func minRefuelStops(target int, startFuel int, stations [][]int) int {
	h := &MaxHeap{}
	heap.Init(h)
	fuel := startFuel
	idx := 0
	stops := 0

	for fuel < target {
		for idx < len(stations) && stations[idx][0] <= fuel {
			heap.Push(h, stations[idx][1])
			idx++
		}

		if h.Len() == 0 {
			return -1
		}

		fuel += heap.Pop(h).(int)
		stops++
	}

	return stops
}

相似题目

题目	难度	考察点
502. IPO	困难	最大堆
1353. 最多可以参加的会议数目	中等	贪心 + 堆
1792. 最大平均通过率	中等	堆
857. 雇佣 K 名工人的最低成本	困难	贪心 + 堆
630. 课程表 III	困难	贪心 + 堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/40069970