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

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

题目描述：

题解：

思路：先全部使用梯子，如果梯子不够用了，则将高度差最短的位置换为砖头。

1.设置一个最小堆gaps记录两个相邻位置的高度差。

2.从下标为0的位置开始，如果当前位置高于或等于下一个位置，则直接下移到下一个位置，否则计算两个位置之间的高度差加入gaps。

3.如果gaps中元素的数量大于ladders，说明此时梯子已经用完，从gaps中取出一个最小值，替换为砖头，如果砖头也被用完，则返回当前位置。

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        gaps = []
        heapq.heapify(gaps)
        for i in range(n-1):
            if heights[i+1]>heights[i]:
                heapq.heappush(gaps,heights[i+1]-heights[i])
                if len(gaps)>ladders:
                    bricks = bricks-heapq.heappop(gaps)
                    if bricks<0:
                        return i
        return n-1