[LeetCode] 1642. 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 <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= 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，高度差最小的在堆顶。这样当梯子用完的时候，我们可以优先去用砖头替换高度差最小的，这样可以尽可能地把砖头利用完。当砖头用完的时候，当前这个 index 就是能去到的最远的地方。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff > 0) {
                queue.offer(diff);
            }
            if (queue.size() > ladders) {
                bricks -= queue.poll();
            }
            if (bricks < 0) {
                return i;
            }
        }
        return heights.length - 1;
    }
}