1642. Furthest Building You Can Reach

想出方法的人是鬼吧

一開始想要greedy, 但答案會錯

看了解答後, 有一種超神的方法

首先, 我們先建立一個priority_queue, 最上面是最小值

然後我們計算每層樓間, 只要需要用到工具的, 我們就把高度差, 往queue裡塞進去

可以用梯子我們就用梯子, 當梯子不夠時, 我們就看那些層, 譬如有一層明明只要一塊磚頭就可以爬上去了, 用梯子浪費, 所以就是把這層用磚頭扣除

當磚頭也用完了, 代表沒招了就要回傳, 但如果可以走完就代表走到最後一棟建築了

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 1;i < heights.size();i++){
            int d = heights[i] - heights[i - 1];
            if(d > 0){
                pq.push(d);
            }
            if(pq.size() > ladders){
                bricks -= pq.top();
                pq.pop();
            }
            if(bricks<0){
                return i - 1;
            }
        }
        return heights.size() - 1;
}
};