可以到达的最远建筑 图解题解
这道题到底在问什么
- 输入
- heights=[4,12,2,7,3,18,20,3,19], bricks=10, ladders=2
- 输出
- 7
最优解：一步一步想明白
- 3记住这句:每次正爬升先当成用梯子塞进最小堆;梯子超额就弹出最小爬升改用砖块;砖块扣到负数就停。下面每一帧都在套它。
- 4从下标 0(高度 4)出发。右边面板是「最小堆」,装着「暂时当成用梯子的那些爬升量」,现在是空的。砖块 10、梯子 2。开始一栋一栋往右看。
- 5站在下标 0(高度 4),看下一栋下标 1(高度 12)。高度差 8。是正爬升,要花资源。
- 6正爬升 8。按套路先当成「用梯子」,把爬升量 8 压进最小堆(右侧高亮新入的那行)。现在堆里有 1 个,等于「暂时占着 1 把梯子」。
- 7占用的梯子数(1)没超过 2,说明梯子还够用,这次爬升 8 就先留在梯子上(留在堆里),不动砖块。继续往右。
- 8站在下标 1(高度 12),看下一栋下标 2(高度 2)。高度差 -10。是下降或持平,无代价。
- 9高度差 -10 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。
- 10站在下标 2(高度 2),看下一栋下标 3(高度 7)。高度差 5。是正爬升,要花资源。
- 11正爬升 5。按套路先当成「用梯子」,把爬升量 5 压进最小堆(右侧高亮新入的那行)。现在堆里有 2 个,等于「暂时占着 2 把梯子」。
- 12占用的梯子数(2)没超过 2,说明梯子还够用,这次爬升 5 就先留在梯子上(留在堆里),不动砖块。继续往右。
- 13站在下标 3(高度 7),看下一栋下标 4(高度 3)。高度差 -4。是下降或持平,无代价。
- 14高度差 -4 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。
- 15站在下标 4(高度 3),看下一栋下标 5(高度 18)。高度差 15。是正爬升,要花资源。
- 16正爬升 15。按套路先当成「用梯子」,把爬升量 15 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。
- 17占用的梯子(3)超过了 2 把。把堆里最小的那次爬升 5 弹出来、改用砖块顶(堆顶最小、最不值得占梯子),砖块从 10 扣到 5,还够,继续往前。
- 18站在下标 5(高度 18),看下一栋下标 6(高度 20)。高度差 2。是正爬升,要花资源。
- 19正爬升 2。按套路先当成「用梯子」,把爬升量 2 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。
- 20占用的梯子(3)超过了 2 把。把堆里最小的那次爬升 2 弹出来、改用砖块顶(堆顶最小、最不值得占梯子),砖块从 5 扣到 3,还够,继续往前。
- 21站在下标 6(高度 20),看下一栋下标 7(高度 3)。高度差 -17。是下降或持平,无代价。
- 22高度差 -17 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。
- 23站在下标 7(高度 3),看下一栋下标 8(高度 19)。高度差 16。是正爬升,要花资源。
- 24正爬升 16。按套路先当成「用梯子」,把爬升量 16 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。
- 25占用的梯子超过 2 把,弹出最小爬升 8 改用砖块,要扣 8 但只剩 3,扣完变成 -5(负数),砖块不够了!
- 26砖块扣成负数,这一步跨不过去了。能稳稳站住的最远下标是 7(绿色那段都到得了,红色那栋够不着)。答案 = 7。
- 27分两种情况看清。第一,若硬要跨到下标 8,就算把两把梯子留给最大的爬升 16 和 15,剩下的爬升 2、5、8 也只能用砖块,共需 2+5+8 = 15 块,超过 10,所以 8 到不了。第二,对真正走过的 0→7 前缀,正爬升是 8、5、15、2,把梯子留给最大的 15 和 8,其余 2 和 5 用砖块,共付 7 块,还剩 3 块。这就是能稳稳到下标 7 的最优分配。
⚠️ 容易写错的地方
✗ 错：下降也当成消耗
✓ 对：只在高度差 > 0 时处理
走到更矮或等高的下一栋无代价,高度差 ≤ 0 的步直接跨过,不进堆、不扣资源
✗ 错：梯子超额时弹堆顶最大
✓ 对：弹出最小爬升改用砖块
梯子要留给最大爬升,所以让出去用砖块的应是当前堆里最小的那次,用最小堆堆顶刚好
✗ 错：砖块扣到 0 就停
✓ 对：扣到余额 < 0 才停
砖块恰好扣到 0 说明这步还能用砖块走完,能站住;只有变成负数才是真的不够、停在上一栋
完整代码（Python / C++ / Java）
Python
from typing import List
import heapq
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
heap = []
for i in range(len(heights) - 1):
climb = heights[i + 1] - heights[i]
if climb > 0:
heapq.heappush(heap, climb)
if len(heap) > ladders:
bricks -= heapq.heappop(heap)
if bricks < 0:
return i
return len(heights) - 1C++
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i + 1 < (int)heights.size(); ++i) {
int climb = heights[i + 1] - heights[i];
if (climb > 0) {
pq.push(climb);
if ((int)pq.size() > ladders) { bricks -= pq.top(); pq.pop(); }
if (bricks < 0) return i;
}
}
return heights.size() - 1;
}
};Java
import java.util.*;
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i + 1 < heights.length; i++) {
int climb = heights[i + 1] - heights[i];
if (climb > 0) {
pq.offer(climb);
if (pq.size() > ladders) bricks -= pq.poll();
if (bricks < 0) return i;
}
}
return heights.length - 1;
}
}复杂度
时间
O(n log(ladders + 1))
遍历 n-1 对相邻建筑;堆里瞬时最多装 ladders+1 个元素,每次入堆、弹堆顶都是 O(log(ladders + 1)),这样 ladders=0 时也不退化
空间
O(ladders + 1)
最小堆最多保留 ladders+1 个仍占着梯子的爬升量;ladders=0 时堆里也会瞬时出现 1 个再被弹出
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 可以到达的最远建筑 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这道贪心要用堆,而不是先扫一遍找出最大的 ladders 次爬升直接分配?+
因为是「能走多远」的前缀问题:你必须按顺序一步步往前,在每个位置都已用最优方式分配好前面的资源,才能判断到这里是否还走得动。一次性挑最大的几次爬升给梯子,无法回答「在第 i 栋时砖块够不够」这个随位置变化的问题。用最小堆边走边维护,正好做到每一步都是当前最优。
砖块判停为什么是「余额小于 0」而不是「等于 0」?+
扣完砖块后如果余额恰好是 0,说明这一步的砖块刚好用完、人已经站到了这一栋,是能到达的;只有扣完变成负数,才说明砖块根本不够铺完这次爬升,人没能跨过去,应停在上一栋,返回当前下标 i。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 可以到达的最远建筑 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。