---
# System prepended metadata

title: 1642. Furthest Building You Can Reach
tags: [Leetcode, Priority Queue, Medium, Greedy]

---

# 1642. Furthest Building You Can Reach
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/furthest-building-you-can-reach/description/
## 思路
遇到跨度大的尽量用梯子 遇到跨度小的尽量用砖头
所以我们把所有跨度放在priority queue里面 如果queue的size大于ladder的数目 我们就pop出来最小的跨度 用砖头补上
直到砖头不够了 就是我们能到达的最远距离
## Code
```java=
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        Queue<Integer> pq = new PriorityQueue<>();
        for(int i=1; i<heights.length; i++){
            if(heights[i-1]>=heights[i]) continue;
            int diff = heights[i]-heights[i-1];
            pq.add(diff);
            if(pq.size()>ladders){
                bricks -= pq.poll();
                if(bricks<0){
                    return i-1;
                }
            }
        }
        return heights.length-1;
    }
}
```