1642. Furthest Building You Can Reach

Leetcode link

解题思路

leetcode 难得有这么幽默的一道题，本题要求我们在屋顶玩跑酷，题目给定我们两个工具：砖块与梯子，其中梯子可以无限延长，而砖块只有固定高度；题目要求我们翻越尽可能多的建筑屋顶，要求是，如果要翻越的建筑比当前建筑低，直接跳下去就完事；如果比当前建筑高，则需要借助砖块或者梯子。

可想而知，梯子是我们想要翻越尽可能多屋顶的最佳选择，所以必须尽可能的 “换” 更多的砖块

至于怎么换呢？我门需要用到贪心的思路，具体步骤如下：

1. 首先我们往前翻越要优先使用砖块
2. 当遇到砖块用完的情况下，我们可以用梯子 “换” 砖块
3. 也就是比较当前高度差以及之前最高的高度差，如果之前的高度差比较大，则用梯子替代掉之前用了最多砖块的地方；否则直接用梯子
4. 重复步骤 1，3 直到砖块梯子都用完且无法前进的时候返回当前下标

C++

class Solution {
public:
  int furthestBuilding(vector<int> &heights, int bricks, int ladders) {
    // 大根堆保存之前翻越每一栋楼用的砖块数量
    priority_queue<int> pq;
    for (int num = 0; num < heights.size() - 1; num++) {
      // 如果即将翻越的大楼比当前大楼低，直接过去就完事
      if (heights[num + 1] <= heights[num]) {
        continue;
      } else {
        // 高度落差
        int altitude = heights[num + 1] - heights[num];
        // 如果当前砖块还够
        if (altitude <= bricks) {
          bricks -= altitude;
          pq.push(altitude);
        } else {
          if (ladders > 0) {
            // 梯子还够的话，用梯子
            ladders--;
            // 如果之前用过的砖块比现在要用的多就用砖块换，否则直接用梯子
            if (!pq.empty() && pq.top() > altitude) {
              bricks += pq.top();
              pq.pop();
              num--;
            }
          } else {
            //  连梯子都无了那就是真的无了
            return num;
          }
        }
      }
    }
    return heights.size() - 1;
  }
};