可以到达的最远建筑
难度:
标签:
题目描述
给你一个整数数组 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
代码结果
运行时间: 79 ms, 内存: 26.5 MB
/*
* 思路：
* 1. 使用Stream处理高度差，保留每一步的差值
* 2. 将所有的高度差过滤并排序
* 3. 依次使用砖块和梯子，并且管理砖块数量超限时的情况
*/
import java.util.PriorityQueue;
import java.util.stream.IntStream;
public class SolutionStream {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int[] diffs = IntStream.range(0, heights.length - 1)
.map(i -> heights[i + 1] - heights[i])
.filter(diff -> diff > 0)
.toArray();
for (int diff : diffs) {
pq.add(diff);
bricks -= diff;
if (bricks < 0) {
if (ladders > 0) {
ladders--;
bricks += pq.poll();
} else {
return pq.size();
}
}
}
return diffs.length;
}
}解释
方法:
本题解采用优先队列（最小堆）策略来动态决定何时使用砖块和何时使用梯子。算法的基本思路是：遍历每个建筑物，并判断是否需要砖块或梯子来到达下一个建筑物。如果下一个建筑物更高，且还有梯子可用，则优先使用梯子，并将所需的高度差加入到最小堆中。如果没有梯子可用，会检查堆中的最小高度差（即最轻松可以用梯子替代的）；如果当前需要的砖块数量（高度差）比堆顶元素还大，会使用砖块替换堆顶的梯子使用，从而节省梯子，否则直接使用砖块。通过这种方式，梯子总是被用在最需要的地方，从而最大化行进的距离。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在决定使用梯子还是砖块时，为什么优先选择使用梯子而不是砖块？
▷🦆
当现有梯子用完后，如何决定是否使用砖块替换堆中已用梯子覆盖的最小高度差？
▷🦆
如果遇到连续的建筑高度增加，算法如何确保梯子和砖块的使用仍然是最优的？
▷