1642.可以到达的最远建筑
难度：中等
题目
给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
提示：
- 1 <= heights.length <= 105
- 1 <= heights[i] <= 106
- 0 <= bricks <= 109
- 0 <= ladders <= heights.length
示例
输入：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
分析
偶然翻到这个题目，力扣难得遇到这么幽默的动图，怎么能不做这道题呢！
那么这道题怎么好理解？我们需要使用贪心的思路来考虑。
下面我讲一个故事来帮你分析这道题。
- 神偷Jacky身上带着一堆砖头和可以无限伸缩的梯子在楼顶穿梭。
- 如果遇到下一个楼顶小于等于当前楼顶，那么直接跳过去就行了
- 但如果遇到下一个楼顶大于当前楼顶爬不上去的时候，如果你是Jacky你用丢砖头还是梯子？
当然是丢砖头了，也许下次遇到的楼比这次高一万倍，那时候再用梯子岂不是更好！ - 丢了足够的砖头，接着往下走，直到砖头都用完了，此时该怎么操作，直接在本次用梯子吗？显然不是！
- 他从之前爬过的大楼中，找到用最多砖头的一次，此时Jacky有一个乾坤大挪移的功法，可以把那次使用砖头吸过来，
用一个梯子弥补砖头。 比如之前最多一次用了100个砖头，而此次使用了2个砖头，那么我们就用1个梯子换来了98块砖头，
可以继续前进了。 - 使用5的贪心方式，走到没梯子砖头也不够的时候，返回当前的大楼需要即可。
听懂了神偷Jacky的贪心思路，那么怎么快速找用掉最多砖头的那一次呢，我们使用堆排序，但由于Python没有大根堆，
所以每次砖头入堆时，需要将其变为负数，才能通过小根堆实现大根堆(这个技巧重复很多次了，大家一定要记住)。
思路分析好了，数据结构也有了，那就开始编码吧！
解题
import heapq
class Solution:
def furthestBuilding(self, heights, bricks, ladders):
hq = []
for i in range(1, len(heights)):
diff = heights[i] - heights[i - 1]
# 只有当前楼层大于前一个楼层我们才需要抄家伙
if diff > 0:
# 通过负数模拟最大堆
heapq.heappush(hq, -diff)
# 优先减砖头
bricks -= diff
if bricks < 0:
# 砖头小于零时找梯子，有梯子交换，没梯子退出
if ladders:
ladders -= 1
# 最大砖头小号出堆，弥补砖头数量
bricks -= heapq.heappop(hq)
else:
return i - 1
return len(heights) - 1
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论