1642. Furthest Building You Can Reach

Question

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.

Solution

贪心算法+优先级队列。

从第二栋楼开始遍历当前位置，下一栋楼与当前位置的高度差为h。
如果h小于0，则无成本前进。
否则如果剩余砖块，则优先使用砖块，并将使用砖块的个数加入大根堆中。
如果剩余砖块不足，且有梯子剩余时，用梯子替换掉小号最多砖块的位置，增加剩余砖块的数量。
如果剩余砖块和梯子都不足，则返回上一个位置。

如果遍历到最后，则返回最后一个建筑物的位置。

Code

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 1; i < heights.length; i++){
            int h = heights[i] - heights[i-1];
            if(h > 0){
                pq.add(h);
                bricks-=h;
                if(bricks < 0){
                    if(ladders > 0){
                        ladders--;
                        bricks += pq.poll();
                    }
                    else{
                        return i-1;
                    }
                }
            }
        }
        return heights.length - 1;
    }
}