可以到达的最远建筑

记住这句:每次正爬升先当成用梯子塞进最小堆;梯子超额就弹出最小爬升改用砖块;砖块扣到负数就停。下面每一帧都在套它。

从下标 0(高度 4)出发。右边面板是「最小堆」,装着「暂时当成用梯子的那些爬升量」,现在是空的。砖块 10、梯子 2。开始一栋一栋往右看。

站在下标 0(高度 4),看下一栋下标 1(高度 12)。高度差 8。是正爬升,要花资源。

正爬升 8。按套路先当成「用梯子」,把爬升量 8 压进最小堆(右侧高亮新入的那行)。现在堆里有 1 个,等于「暂时占着 1 把梯子」。

占用的梯子数(1)没超过 2,说明梯子还够用,这次爬升 8 就先留在梯子上(留在堆里),不动砖块。继续往右。

站在下标 1(高度 12),看下一栋下标 2(高度 2)。高度差 -10。是下降或持平,无代价。

高度差 -10 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。

站在下标 2(高度 2),看下一栋下标 3(高度 7)。高度差 5。是正爬升,要花资源。

正爬升 5。按套路先当成「用梯子」,把爬升量 5 压进最小堆(右侧高亮新入的那行)。现在堆里有 2 个,等于「暂时占着 2 把梯子」。

占用的梯子数(2)没超过 2,说明梯子还够用,这次爬升 5 就先留在梯子上(留在堆里),不动砖块。继续往右。

站在下标 3(高度 7),看下一栋下标 4(高度 3)。高度差 -4。是下降或持平,无代价。

高度差 -4 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。

站在下标 4(高度 3),看下一栋下标 5(高度 18)。高度差 15。是正爬升,要花资源。

正爬升 15。按套路先当成「用梯子」,把爬升量 15 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。

占用的梯子(3)超过了 2 把。把堆里最小的那次爬升 5 弹出来、改用砖块顶(堆顶最小、最不值得占梯子),砖块从 10 扣到 5,还够,继续往前。

站在下标 5(高度 18),看下一栋下标 6(高度 20)。高度差 2。是正爬升,要花资源。

正爬升 2。按套路先当成「用梯子」,把爬升量 2 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。

占用的梯子(3)超过了 2 把。把堆里最小的那次爬升 2 弹出来、改用砖块顶(堆顶最小、最不值得占梯子),砖块从 5 扣到 3,还够,继续往前。

站在下标 6(高度 20),看下一栋下标 7(高度 3)。高度差 -17。是下降或持平,无代价。

高度差 -17 ≤ 0,走到更矮(或一样高)的下一栋无代价,直接跨过去,堆原封不动。继续看下一步。

站在下标 7(高度 3),看下一栋下标 8(高度 19)。高度差 16。是正爬升,要花资源。

正爬升 16。按套路先当成「用梯子」,把爬升量 16 压进最小堆(右侧高亮新入的那行)。现在堆里有 3 个,等于「暂时占着 3 把梯子」。

占用的梯子超过 2 把,弹出最小爬升 8 改用砖块,要扣 8 但只剩 3,扣完变成 -5(负数),砖块不够了!

砖块扣成负数,这一步跨不过去了。能稳稳站住的最远下标是 7(绿色那段都到得了,红色那栋够不着)。答案 = 7。

分两种情况看清。第一,若硬要跨到下标 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 仍算到达。