力扣 1642. 可以到达的最远建筑 [堆]

1642. 可以到达的最远建筑

给你一个整数数组 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 <= 105
• 1 <= heights[i] <= 106
• 0 <= bricks <= 109
• 0 <= ladders <= heights.length

题解

来自这里(hw_wt)

优先队列解题

1、遍历过程求解建筑高度差，在需要使用梯子或者砖的时候，优先使用梯子保证后可以向后移动。

2、同时在梯子不足的时候，使用砖块替换前面的梯子，直到不能替换为止，这个时候应该就是弹尽粮绝的时候了。

至于代码的写法，通过一个优先队列来维护遍历过程中高度差，维持队列长度不能超过梯子数，超过时说明队列中存在一个最小的高度差，尝试用砖块替换。

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int idx=0;
        priority_queue<int,vector<int>,greater<int>> pq;
        while(idx<heights.size()-1){
            int diff=heights[idx]-heights[idx+1];
            if(diff>=0){
                idx++;
            }
            else{
                pq.push(-diff);//取反加入
                if(pq.size()>ladders){//梯子用完了，取出差距最小的用砖头去填
                    bricks-=pq.top();
                    pq.pop();
                }
                if(bricks<0){//砖头填完了还是不够，无法前进
                    return idx;
                }
                idx++;//砖头还有，就继续前进
            }
        } 
        return idx; 
    }
};