可以到达的最远建筑

标签: 贪心 数组 堆（优先队列）

难度: Medium

给你一个整数数组 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

Submission

运行时间: 79 ms

内存: 26.5 MB

import heapq
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        gaps = []
        heapq.heapify(gaps)
        n = len(heights)
        pos = 0
        while pos < n - 1:
            # print(gaps)
            if heights[pos + 1] <= heights[pos]:
                pos += 1
            else:
                if ladders > 0:
                    ladders -= 1
                    heapq.heappush(gaps, heights[pos + 1] - heights[pos])
                    pos += 1
                else:
                    now_gap = heights[pos + 1] - heights[pos]
                    if len(gaps) != 0 and gaps[0] < now_gap:
                        min_gap = heapq.heappop(gaps)
                        heapq.heappush(gaps, now_gap)
                        now_gap = min_gap
                    if now_gap <= bricks:
                        bricks -= now_gap
                        pos += 1
                    else:
                        break
                    
        return pos

Explain

本题解采用优先队列（最小堆）策略来动态决定何时使用砖块和何时使用梯子。算法的基本思路是：遍历每个建筑物，并判断是否需要砖块或梯子来到达下一个建筑物。如果下一个建筑物更高，且还有梯子可用，则优先使用梯子，并将所需的高度差加入到最小堆中。如果没有梯子可用，会检查堆中的最小高度差（即最轻松可以用梯子替代的）；如果当前需要的砖块数量（高度差）比堆顶元素还大，会使用砖块替换堆顶的梯子使用，从而节省梯子，否则直接使用砖块。通过这种方式，梯子总是被用在最需要的地方，从而最大化行进的距离。

时间复杂度: O(n log n)

空间复杂度: O(n)

import heapq


class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        gaps = []  # 存放使用梯子覆盖的高度差
        heapq.heapify(gaps)  # 初始化最小堆
        n = len(heights)  # 获取建筑物的数量
        pos = 0  # 当前位置
        while pos < n - 1:  # 遍历所有建筑物
            # 比较当前建筑物与下一个建筑物的高度
            if heights[pos + 1] <= heights[pos]:
                pos += 1  # 如果下一个建筑物不高于当前，直接前进
            else:
                if ladders > 0:
                    ladders -= 1  # 使用一个梯子
                    heapq.heappush(gaps, heights[pos + 1] - heights[pos])  # 将高度差加入堆中
                    pos += 1
                else:
                    now_gap = heights[pos + 1] - heights[pos]  # 需要的砖块数量
                    if len(gaps) != 0 and gaps[0] < now_gap:
                        min_gap = heapq.heappop(gaps)  # 使用砖块替换最小的堆顶元素（最不值得用梯子的地方）
                        heapq.heappush(gaps, now_gap)
                        now_gap = min_gap
                    if now_gap <= bricks:
                        bricks -= now_gap  # 使用砖块
                        pos += 1
                    else:
                        break  # 没有足够的砖块，结束循环
        return pos  # 返回最远到达的位置

Explore

在处理高度增加的情况下，优先选择使用梯子而不是砖块的主要原因是梯子可以覆盖任意高度差，而且使用梯子不会消耗砖块资源。这种策略使得梯子被用于最大的高度差，从而保留砖块以用于其他较小但仍需要额外资源的高度差。总的来说，这样做可以在资源有限的情况下尽可能延伸可到达的距离。

当梯子用完后，如果遇到一个需要更多砖块的高度差，算法会考虑从最小堆中移除当前最小的高度差（即之前用梯子覆盖的最不划算的部分），并用砖块来覆盖这个较小的高度差，同时使用梯子覆盖新的更大的高度差。这种策略确保了梯子总是被用于最需要的地方，而砖块则被用于较小的高度差，从而延伸可到达的最远距离。

算法通过持续维护一个最小堆来确保梯子和砖块的使用最优化。最小堆中存储的是使用梯子覆盖的高度差。每次遇到需要更多资源的高度差时，算法都会评估当前资源（梯子和砖块）的使用情况，并决定是否重新分配这些资源。通过将梯子用于当前已知的最大高度差，以及用砖块填补其他较小的高度差，算法能够确保在资源有限的条件下，达到最远的建筑。