LeetCode 1642. 可以到达的最远建筑

Categories:

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

题目描述

✅ 1642. 可以到达的最远建筑

思路分析

解法一：最小堆（推荐）

核心思路：

记录每次上升的高度差，优先用梯子覆盖更大的上升。

将高度差加入最小堆，若堆大小超过梯子数，则用砖块覆盖堆顶最小差值。

砖块不足时停止，当前位置即为最远可达。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示建筑数量。

空间复杂度：O(n)，用于堆存储。

import java.util.PriorityQueue;

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff <= 0) {
                continue;
            }

            minHeap.offer(diff);
            if (minHeap.size() > ladders) {
                bricks -= minHeap.poll();
                if (bricks < 0) {
                    return i;
                }
            }
        }

        return heights.length - 1;
    }
}

import "container/heap"

type MinHeap []int

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

func furthestBuilding(heights []int, bricks int, ladders int) int {
	h := &MinHeap{}
	heap.Init(h)

	for i := 0; i < len(heights)-1; i++ {
		diff := heights[i+1] - heights[i]
		if diff <= 0 {
			continue
		}

		heap.Push(h, diff)
		if h.Len() > ladders {
			bricks -= heap.Pop(h).(int)
			if bricks < 0 {
				return i
			}
		}
	}

	return len(heights) - 1
}

相似题目

题目	难度	考察点
871. 最低加油次数	困难	贪心/堆
502. IPO	困难	堆
1046. 最后一块石头的重量	简单	堆
295. 数据流的中位数	困难	双堆
215. 数组中的第K个最大元素	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/35832532