LeetCode 5556. 可以到达的最远建筑
给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块 如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
示例 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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/furthest-building-you-can-reach 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题 最开始用的 递归 很明显会超时 然后果然超时了
然后改成了贪心
能用梯子的时候用梯子，不能用的时候 把之前读取的 差值中选择最小的 用砖头
使用优先队列，每次弹出最大值，因为我们需要最小值，所以以负数进行存储。
class Solution {
public:
priority_queue<int> que;
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int n= heights.size(),ans=0;
long long sum = 0;
while(!que.empty()) que.pop();
for(int i=1;i<n;i++){
if(heights[i-1]>=heights[i]){
}else{
int cha = heights[i]-heights[i-1];
que.push(-cha);
while(que.size()>ladders){
sum = sum - que.top();
que.pop();
}
if(sum>bricks) break;
}
ans = i;
}
return ans;
}
};或者是使用 multiset<int> s; 可以重复的set
class Solution {
multiset<int> s;
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int n=heights.size(),i;
s.clear();
for(i=0;i+1<n;i++)if(heights[i+1]>heights[i])
{
s.insert(heights[i+1]-heights[i]);
if(s.size()>ladders)
{
bricks-=*s.begin();
if(bricks<0)break;
s.erase(s.begin());
}
}
return i;
}
};