原文链接: https://leetcode-cn.com/problems/furthest-building-you-can-reach
英文原文
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i+1 (0-indexed),
- If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
- If the current building's height is less than the next building's height, you can either use one ladder or
(h[i+1] - h[i])bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 Output: 4 Explanation: Starting at building 0, you can follow these steps: - Go to building 1 without using ladders nor bricks since 4 >= 2. - Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7. - Go to building 3 without using ladders nor bricks since 7 >= 6. - Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9. It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0 Output: 3
Constraints:
1 <= heights.length <= 1051 <= heights[i] <= 1060 <= bricks <= 1090 <= ladders <= heights.length
中文题目
给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
- 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
- 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或
(h[i+1] - h[i])个砖块
示例 1：
输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 输出：4 解释：从建筑物 0 出发，你可以按此方案完成旅程： - 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2 - 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7 - 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6 - 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9 无法越过建筑物 4 ，因为没有更多砖块或梯子。
示例 2：
输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 输出：7
示例 3：
输入：heights = [14,3,19,3], bricks = 17, ladders = 0 输出：3
提示：
1 <= heights.length <= 1051 <= heights[i] <= 1060 <= bricks <= 1090 <= ladders <= heights.length
通过代码
高赞题解
前言
这道题好像数据又太弱了？所有不基于优先队列（直接排序也行）的贪心算法都是错的，可以试试下面这组测试数据：
[1,5,1,2,3,4]
4
1方法一：优先队列 + 贪心
思路与算法
在移动的过程中，我们会需要若干次需要使用砖块或者梯子的情况。假设当前我们需要移动到下一建筑物，但必须使用 $1$ 架梯子或者 $\Delta h$ 个砖块，那么我们如何抉择是使用梯子还是砖块呢？
我们可以用贪心的思路来想这个问题。「梯子」相当于一次性的无限量砖块，那么我们一定是把梯子用在刀刃上。也就是说，如果我们有 $l$ 架梯子，那么我们会在 $\Delta h$ 最大的那 $l$ 次使用梯子，而在剩余的情况下使用砖块。
这样一来，我们就可以得到正确的算法了：我们使用优先队列实时维护不超过 $l$ 个最大的 $\Delta h$，这些就是使用梯子的地方。对于剩余的 $\Delta h$，我们需要使用砖块，因此需要对它们进行累加，如果某一时刻这个累加值超过了砖块的数目 $b$，那么我们就再也无法移动了。
代码
[sol1-C++]class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders) { int n = heights.size(); // 由于我们需要维护最大的 l 个值，因此使用小根堆 priority_queue<int, vector<int>, greater<int>> q; // 需要使用砖块的 delta h 的和 int sumH = 0; for (int i = 1; i < n; ++i) { int deltaH = heights[i] - heights[i - 1]; if (deltaH > 0) { q.push(deltaH); // 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块 if (q.size() > ladders) { sumH += q.top(); q.pop(); } if (sumH > bricks) { return i - 1; } } } return n - 1; } };
[sol1-Python3]class Solution: def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: n = len(heights) # 由于我们需要维护最大的 l 个值，因此使用小根堆 q = list() # 需要使用砖块的 delta h 的和 sumH = 0 for i in range(1, n): deltaH = heights[i] - heights[i - 1] if deltaH > 0: heapq.heappush(q, deltaH) # 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块 if len(q) > ladders: sumH += heapq.heappop(q) if sumH > bricks: return i - 1 return n - 1
复杂度分析
时间复杂度：$O(n \log l)$，其中 $n$ 是建筑物的数量，$l$ 是梯子的数量。
空间复杂度：$O(l)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6810 | 15062 | 45.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
