[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:
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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
}

[LeetCode] 1642. Furthest Building You Can Reach
https://shurui91.github.io/posts/13153578.html
Author
Aaron Liu
Posted on
May 13, 2021
Licensed under