1642-可以到达的最远建筑

Raphael Liu Lv10

给你一个整数数组 heights ,表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders

你从建筑物 0 开始旅程,不断向后面的建筑物移动,期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1(下标 从 0 开始 )时:

  • 如果当前建筑物的高度 大于或等于 下一建筑物的高度,则不需要梯子或砖块
  • 如果当前建筑的高度 小于 下一个建筑的高度,您可以使用 一架梯子(h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块,返回你可以到达的最远建筑物的下标(下标 从 0 开始 )。

示例 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 <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= heights.length

思路

对比普通的二分无非就多了一个额外操作:每次开辟一个包含 mid 和前面的楼的 高度差 数组,利用这个数组排序后可以在每次 check 中先枚举最高的高度进行优先选择,其次搭砖,从而查看当前 mid 位置是否合理

代码

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
int len = heights.length;
if(ladders >= len - 1) return len - 1;
// 对走到最远的下标进行二分
int l = ladders, r = len - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(heights, bricks, ladders, mid)) l = mid;
else r = mid - 1;
}
return l;
}
public boolean check(int[] heights, int bricks, int ladders, int mid) {
// 建立 mid 之前的高度差数组,方便最优化搭砖
int[] dist = new int[mid];
for(int i = 0; i < mid; i++) dist[i] = heights[i + 1] - heights[i];
Arrays.sort(dist);

// 从最高的高度差进行枚举
for(int i = mid - 1; i >= 0; i--) {
// 提前可以剪波枝
if(dist[i] < 0) break;
if(ladders > 0) ladders--;
else if(bricks >= dist[i]) bricks -= dist[i];
else return false;
}
return true;
}
}
 Comments
On this page
1642-可以到达的最远建筑