leetcode：1642. 可以到达的最远建筑

题目

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度小于下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

示例 1：
[中等] 1642. 可以到达的最远建筑 - 图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

输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3

解答 & 代码

解法 0：三维动态规划（超时）

动态规划：

动态规划数组 **dp**：dp[i][b][l] 代表有 b 块砖和 l 架梯子，能否到达建筑物 i
状态转移方程：
- 若 heights[i] <= heights[i - 1]，则 dp[i][b][l] = dp[i - 1][b][l]
- 若 heights[i] > heights[i - 1]，则 dp[i][b][l] = dp[i - 1][b - (heights[i] - heights[i - 1])][l] || dp[i - 1][b][l - 1]
  - 若 b - (heights[i] - heights[i - 1] < 0，则 dp[i - 1][b - (heights[i] - heights[i - 1])][l] = false
  - 若 l - 1 < 0，则 dp[i - 1][b][l - 1] = false

初始化：dp[0][b][l] = true，即建筑物 0 肯定能到达

class Solution {
public:
  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
      int len = heights.size();
      vector<vector<vector<bool>>> dp(len, vector<vector<bool>>(bricks + 1, vector<bool>(ladders + 1, true)));
      for(int i = 1; i < len; ++i)
      {
          for(int b = 0; b <= bricks; ++b)
          {
              for(int l = 0; l <= ladders; ++l)
              {
                  if(heights[i] <= heights[i - 1])
                      dp[i][b][l] = dp[i - 1][b][l];
                  else
                  {
                      bool candidate1 = false;
                      bool candidate2 = false;
                      int heightDiff = heights[i] - heights[i - 1];
                      if(b - heightDiff >= 0)
                          candidate1 = dp[i - 1][b - heightDiff][l];
                      if(l - 1 >= 0)
                          candidate2 = dp[i - 1][b][l - 1];
                      dp[i][b][l] = candidate1 || candidate2;
                  }
              }
          }
          // 如果不能到达建筑物 i，则返回 i - 1
          if(dp[i][bricks][ladders] == false)
              return i - 1;
      }
      return len - 1;
  }
};

解法 1：贪心法 + 优先队列

贪心思想：梯子相当于无限块砖头，因此 l 架梯子应该用在高度差 top l 的 l 次移动，而在其余情况使用砖头。

可以在前 l 次升高的移动时，都先使用梯子，同时记录每次移动的高度差。之后的每次移动再需要升高时，将之前高度差最小的移动方式从梯子改为砖头。如果当前剩余砖头数小于最小高度差，则无法到达当前位置

使用优先队列（小根堆）存储每次移动的高度差（高度降低时无需存储），便于后续每次取最小值

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int len = heights.size();
        priority_queue<int, vector<int>, greater<int>> minHeap;        // 小根堆，存储高度差
        for(int i = 1; i < len; ++i)
        {
            if(heights[i] > heights[i - 1])
            {
                // 前 l 次升高的移动先用梯子，并用小根堆记录高度差
                if(ladders > 0)
                {
                    --ladders;
                    minHeap.push(heights[i] - heights[i - 1]);
                }
                // 若梯子已用完，还需要往高处移动
                else if(ladders == 0)
                {
                    minHeap.push(heights[i] - heights[i - 1]);    // 将当前高度差存入小根堆
                    int minDiff = minHeap.top();                // 取最小高度差
                    minHeap.pop();
                    // 如果最小高度差大于剩余砖头数，则说明无法到达当前位置，直接返回 i - 1
                    if(minDiff > bricks)
                        return i - 1;
                    // 在最小高度差所在的那次移动，用砖头代替梯子，减少相应的砖头数
                    bricks -= minDiff;
                }
            }
        }
        return len - 1;
    }
};

复杂度分析：设共 n 栋建筑，共 l 架梯子

时间复杂度 O(n log(l + 1))：小根堆最多存储 l + 1 个高度差
空间复杂度 O(l)：小根堆最多存储 l + 1 个高度差

执行结果：

执行结果：通过

执行用时：124 ms, 在所有 C++ 提交中击败了 7.30% 的用户
内存消耗：52.4 MB, 在所有 C++ 提交中击败了 48.17% 的用户