1642_可以到达的最远建筑

类型：堆

1. 可以到达的最远建筑 💛 ⭐
https://leetcode-cn.com/problems/furthest-building-you-can-reach/

❓ 你有 bricks 块砖块和 ladders 根梯子。整数数组 heights 表示建筑物的高度，你从 0 号建筑开始往后爬。
- 当下一个建筑不高于当前建筑时，你可以直接过去。
- 当下一个建筑比当前建筑高 x 个单位时，你可以通过消耗 x 个砖块，或一根梯子爬过去。
合理利用砖块和建筑，求你最远能达到的建筑的下标。

💡 堆（事后诸葛亮）

此题的关键在于如何运用好梯子，砖块是很灵活的，填在哪里都没什么区别，而梯子相当于无穷的方块，不过用一次少一根。我们当然是希望好梯用在刀刃上。

此题其实和「871. 最低加油次数」是类似的，用梯子就好比是加油，掌握好了用梯子的时机，也就得到了最佳的结果。

如同题 871 中尝试不加油一样，我们在此题中也尝试不使用梯子，当走到某个地方砖块不够了，我们再找出之前消耗砖块最多的地方，换成使用梯子。这样我们就能保证每次梯子的使用都是最关键的。
```
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        h = []

        for i in range(1, len(heights)):
            diff = heights[i] - heights[i - 1]

            if diff <= 0:
                continue

            if bricks < diff and ladders > 0:
                # 要用梯子了，可能是用在此处，也可能是用在之前的最高处
                ladders -= 1
                if h and -h[0] > diff:
                    bricks -= heapq.heappop(h)
                else:
                    continue

            bricks -= diff
            if bricks < 0:
                return i - 1
            heapq.heappush(h, -1 * diff)
        return len(heights) - 1
```