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]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/furthest-building-you-can-reach
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路是贪心，具体做法如下。对于每一个位置 i 而言，如果他的下一个位置 i + 1 的高度比自己要矮，那么我们不需要消耗梯子或者砖头；反之如果他的下一个位置 i + 1 的高度比自己要高，我们就需要消耗梯子或者砖头。由于梯子的高度是任意的同时砖头的数量是有限的，所以这里我们先用梯子，当梯子用完之后，我们看看用过梯子的地方是否有可能被砖头替换掉，这样我们就可以利用省下的梯子再去走更远的距离。
所以这里我们需要一个最小堆，堆中记录的是每一个需要梯子/砖头的高度差 diff，高度差最小的在堆顶。这样当梯子用完的时候，我们可以优先去用砖头替换高度差较小的，这样可以尽可能地把砖头利用完。
时间O(nlogn)
空间O(n)
Java实现
1 class Solution { 2 public int furthestBuilding(int[] heights, int bricks, int ladders) { 3 PriorityQueue<Integer> queue = new PriorityQueue<>(); 4 for (int i = 0; i < heights.length - 1; i++) { 5 int diff = heights[i + 1] - heights[i]; 6 if (diff > 0) { 7 queue.offer(diff); 8 } 9 if (queue.size() > ladders) { 10 bricks -= queue.poll(); 11 } 12 if (bricks < 0) { 13 return i; 14 } 15 } 16 return heights.length - 1; 17 } 18 }