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

2022-10-11 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

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

题意分析

一排建筑从左往右站着，人只能从当前这栋走到紧邻的下一栋，不能跳过任何一栋，也不能往回走。所以「能到达的最远下标」等价于「从 0 开始连续通过了多少段相邻间隔」。

只有下一栋更高时才需要付出代价：要么消耗 bricks 中恰好等于高度差的砖块数，要么消耗一架梯子。下一栋更低或者一样高时白走，不花任何资源。这一条把问题从「n 栋建筑」缩到「所有正的相邻高度差」。

关键的不对称在于两种资源的计价方式：砖块按高度差论量，爬 10 米就掉 10 块；梯子按次数论，无论爬 1 米还是 100 万米都只用掉 1 架。资源都是全局共享的，用在前面就没法用在后面。

题目问的是能走到的最远下标而不是能否走完，因此答案是「第一次付不起代价的位置」，而不是失败就返回 -1。边界包括：只有一栋建筑时直接返回 0；全程下坡时砖块梯子一块都不用；以及梯子数量已经不少于正差个数时，砖块可以完全不动。

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

核心思路

暴力做法是枚举哪些上坡用梯子：正差有 $k$ 段，从中选 $\min(k, l)$ 段配梯子，其余用砖块，组合数是 $\binom{k}{l}$ 级别，指数爆炸，完全不可行。

瓶颈在于「选择哪几段」被当成了自由组合。观察一下就会发现它其实没有自由度：假设最终走到了某个下标，用掉的梯子集合是 $S$，如果 $S$ 里某段的高度差比某段砖块支付的还小，把这两段的支付方式互换，砖块消耗只会减少不会增加，仍然合法。反复交换到不能再换，就得到结论——梯子一定应该配给当前见过的最大的那几段上坡。

于是维护一个只装「暂定用梯子」的最小堆，把这个结论变成可以边走边执行的规则。不变量是：每处理完一段上坡，堆里恰好装着到此为止所有正高度差中最大的至多 $l$ 段，堆外的那些已经全部用砖块付过账，而 bricks 是剩余砖块数。

维持这个不变量的动作很简单：新来的正差先无条件入堆，若堆的大小超过 $l$，说明装不下了，此时堆顶就是堆内最小的那一段，把它挤出去改用砖块支付。被挤出去的一定是当前最该用砖块的那段，因为堆里剩下的每一段都不比它小。砖块不够时，当前这段就是走不过去的第一道坎。

解题步骤

建一个空的最小堆，它存放的语义是「目前暂定分配给梯子的上坡高度差」。选最小堆而不是最大堆，是因为需要随时取出堆内最小的那段来降级为砖块支付。

从 i = 0 遍历到 n - 2，每次算 diff = heights[i + 1] - heights[i]。循环到 n - 2 是因为下标 n - 1 之后没有下一栋，不存在需要支付的间隔。

diff <= 0 时直接跳过。平走和下坡不消耗资源，把它们塞进堆只会挤占梯子名额，导致后面真正的陡坡付不起。

正的 diff 先无条件入堆。先入堆再判断，是因为新来的这一段有可能比堆里所有元素都大，必须让它参与「谁最该用梯子」的竞争。

入堆后若堆的大小超过 ladders，弹出堆顶，从 bricks 里扣掉这个值。堆顶是当前最小的候选，用砖块支付它的代价最低，这正是贪心交换论证的直接落地。

扣完若 bricks < 0，说明这一段实在过不去，返回 i——注意返回的是当前下标而不是 i + 1，因为人卡在第 i 栋楼上，根本没能踏上第 i + 1 栋。

循环正常跑完，说明每一段都付得起，返回 heights.length - 1。

以 heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 走一遍：堆初始为空，剩余砖块 10。$i = 0$，$diff = 8 > 0$，入堆得 ${8}$，大小 1 不超过 2，不动。$i = 1$，$diff = 2 - 12 = -10 \le 0$，跳过。$i = 2$，$diff = 5$，入堆得 ${5, 8}$，大小 2 不超过 2。$i = 3$，$diff = 3 - 7 = -4$，跳过。$i = 4$，$diff = 15$，入堆得 ${5, 8, 15}$，大小 3 超过 2，弹出堆顶 5，砖块变成 $10 - 5 = 5$，非负，继续；堆剩 ${8, 15}$。$i = 5$，$diff = 2$，入堆得 ${2, 8, 15}$，大小 3 超标，弹出堆顶 2，砖块变成 $5 - 2 = 3$，非负；堆剩 ${8, 15}$。$i = 6$，$diff = 3 - 20 = -17$，跳过。$i = 7$，$diff = 19 - 3 = 16$，入堆得 ${8, 15, 16}$，大小 3 超标，弹出堆顶 8，砖块变成 $3 - 8 = -5 < 0$，返回 $i = 7$。最终两架梯子落在高度差 15 和 16 这两段上，砖块付掉了 5 和 2，正好是「大的给梯子、小的给砖块」。

代码实现

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;
    }
}

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 + 1))$，其中 $n$ 是建筑数、$l$ 是梯子数。每段间隔最多触发一次入堆和一次弹出，堆内元素始终不超过 $l + 1$ 个，单次堆操作是 $O(\log (l + 1))$。

空间复杂度：$O(l)$，堆里最多同时存在 $l + 1$ 段爬升高度，除此之外只有几个标量变量。

关键点总结

两种资源的计价维度不同（砖块按量、梯子按次）时，稀缺且「不看量」的那种一定要留给代价最大的场合，这是贪心交换论证的典型形态。

贪心的正确性靠交换论证说明：任取一个最优方案，把梯子和砖块的分配对调成「梯子配大坡」，砖块消耗单调不增，所以贪心解不劣于任何方案。

最小堆的作用是「维护当前最大的 k 个」，堆顶是这批候选里的淘汰对象。想留最大的一批就用最小堆，方向别记反。

先入堆再判超限，比先判断再决定是否入堆更简洁，也自动处理了「新来的这段本身就该淘汰」的情形。

失败时返回当前下标 i 而不是 i + 1，这类「最远可达位置」的下标口径面试时最好当场跟面试官对齐。

面试视角：这题真正被考的是能否说清贪心为什么对。只报出「最小堆 + 超限弹出」而讲不出交换论证，通常会被追问到答不上来；反过来，把交换论证讲清楚后代码几乎是自明的。

易错点总结

错误写法：把 diff <= 0 的间隔也塞进堆：heights = [4,2,7], bricks = 0, ladders = 1 → 高度差 -2 占掉唯一的梯子名额，高度差 5 被挤出去要用砖块，砖块为 0 直接返回 1，而正确答案是 2。

错误写法：用最大堆保存待定的梯子分配 → 每次淘汰的是最大的那段上坡，砖块被拿去付最贵的坡，砖块消耗被放大，返回的下标偏小。

错误写法：先判断堆是否已满、满了就不让新元素入堆 → 后面出现的超大坡永远进不了梯子集合，等于按先来后到分配梯子，完全丢掉贪心。

错误写法：bricks < 0 时返回 i + 1 → 人其实卡在第 i 栋，[4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 会输出 8 而不是 7。

错误写法：循环写成 i < heights.length 并访问 heights[i + 1] → 最后一次迭代越界，Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。

错误写法：判断条件写成 minHeap.size() >= ladders → 梯子只被用掉 $l - 1$ 架，白白浪费一架，砖块提前耗尽。

错误写法：先扣砖块再判断是否超出堆容量，顺序颠倒 → 堆还没满时就开始花砖块，梯子留到最后反而配给了小坡。

错误写法：bricks 声明成 int 但用等于 0 判空、写成 bricks - top < 0 之外的 bricks < top 却忘了同步扣减 → 剩余砖块没更新，后续判断全部基于陈旧值，能走到的下标被高估。

错误写法：漏掉「循环正常结束」的返回，只在失败分支返回 → 全程资源充足时函数落到末尾，返回默认值 0 或编译报错。

相似题目

题目	难度	考察点
502. IPO	困难	双堆配合，按资本解锁项目后取利润最大者
630. 课程表 III	困难	先按截止时间排序，超时就反悔弹出耗时最长的课程
871. 最低加油次数	困难	把途经加油站存堆里，油不够时再回头取最大的一桶
253. 会议室 II	中等	堆顶维护最早结束时间，决定复用还是新开房间
703. 数据流中的第 K 大元素	简单	固定容量最小堆，堆顶即答案，是本题堆用法的最小模型
1046. 最后一块石头的重量	简单	大顶堆反复取两块相撞，结果再放回堆中