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

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 微软 快手
标签
数组 贪心 堆（优先队列）

题目描述

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

image-20260928230743107

image-20260928230743108

image-20260928230743109

题意分析

从下标零的建筑出发，只能依次走到下一栋。下一栋不更高时免费通行；更高时，要么使用等于高度差数量的砖块，要么使用一架梯子，不论这一段上升多高。

砖块和梯子都会消耗，求最多能到达的建筑下标。梯子的价值取决于替代了多少砖，不能看到上升就固定消耗梯子而不考虑后续更大上升。

解法：最小堆维护梯子分配

核心思路

[!blue]

对已经走过的一段路线，上升高度已经确定。为了让砖块花得最少，梯子应分配给其中最大的若干段：如果某架梯子用于较小上升，而较大上升在用砖，交换它们的支付方式只会减少砖块消耗，不影响可达性。

用最小堆保存当前暂时交给梯子的上升高度。遇到新的正高度差，先加入堆，假设也用梯子。若数量超过梯子总数，弹出最小高度差，改由砖块支付。剩下的始终是目前最值得用梯子的较大上升。

这相当于允许重新安排此前梯子的用途，代码并不需要实际倒退。新上升若较小，就被自己弹出并付砖；新上升若较大，就让此前较小的一段改付砖，腾出梯子给新段。两种情况统一由弹出最小值完成。

处理每条边后，这套安排都使到达下一栋所需的砖块最少。若连这个最少用量都超过预算，其他分配也无法跨过当前边，最远就是当前出发建筑 i；反之可以继续。砖块恰好用完仍然合法，只有变成负数才失败。

解题步骤

  1. 创建空最小堆，依次检查相邻建筑高度差。
  2. 高度差不为正时直接继续，不消耗任何资源。
  3. 将正高度差加入堆，暂作梯子候选。
  4. 堆大小超过梯子数时，弹出最小高度差并从砖块中扣除。
  5. 砖块不足立即返回当前下标；所有边都能通过则返回最后下标。

代码实现

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 int, j int) bool {
    return h[i] < h[j]
}

func (h MinHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

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

    for i := 0; i < len(heights)-1; i++ {
        diff := heights[i+1] - heights[i]
        // 平地和下坡不消耗资源，也不加入分配候选。
        if diff <= 0 {
            continue
        }

        // 先把当前上升暂交给梯子，超额后再淘汰最小上升。
        heap.Push(minHeap, diff)
        if minHeap.Len() > ladders {
            // 超出梯子名额时，把最小上升改为用砖。
            bricks -= heap.Pop(minHeap).(int)
            if bricks < 0 {
                // 无法跨过当前边，最远仍是出发建筑。
                return i
            }
        }
    }

    return len(heights) - 1
}

复杂度分析

  • 时间复杂度：$O(n\log(L+2))$，其中 $L$ 是梯子数。每段上升至多入堆一次、出堆一次，堆临时大小至多为 $L+1$。
  • 空间复杂度：$O(\min(n,L+1))$，保存梯子候选高度差。

关键点总结

[!green]

  • 梯子分配给大上升，砖块支付小上升，交换论证保证当前分配最省砖。
  • 最小堆动态保留最大的若干差值，无需提前知道后面的地形。
  • 当前最省砖方案仍失败，就能确定所有分配都无法跨过这条边。

易错点总结

[!yellow]

  • 下降差值加入堆再扣除，会错误地让砖块增加，只处理正高度差。
  • 弹出最大上升来付砖，会反过来把梯子浪费在小上升。
  • 首次用梯子后就不允许调整，会错过将它换给更大上升的更优安排。
  • 跨不过从 i 到 i+1 的边时返回 i，不能返回尚未到达的建筑。
  • 剩余砖块等于零不是失败，只有小于零才超过预算。

相似题目

题目 难度 关联与区别
871. 最低加油次数 困难 同样将稀缺资源优先用于收益最大的已遇需求，本题把梯子留给最大上升高度。
215. 数组中的第K个最大元素 中等 用小顶堆维护最大的L个上升量，其余上升消耗砖块，复用动态TopK选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/35832532
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！