leetcode 1642. 可以到达的最远建筑-Furthest Building You Can Reach

Problem: 1642. 可以到达的最远建筑-Furthest Building You Can Reach

优先队列堆，最大堆，最大值在堆顶，每次拿到差值height[i-1]-height[i]，若差值divid < 0，则放入堆中，堆中保留差值最小的数字（负数的绝对值越大，该负数越小）（最小的几个负数用梯子），（最大的那些负数用砖块）

若堆的尺寸 > ladders，表示需要pop掉更大的负数(绝对值小)，此时用砖块填充 bricks += pq.top()，若剩下的砖块 <0，则不可以继续了，直接返回i-1

最后返回n-1

Code

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