跳转至

1642. 可以到达的最远建筑#

问题描述#

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

解题思路#

能够到达当前位置的条件是：

  1. 在到达当前位置（包括当前位置）时经历过的前 ladders 个 最大 的高度差之和
  2. 加上 bricks
  3. 大于等于 经历过的所有高度差之和

因为需要保存最大的前多少个数，所以使用优先队列保存。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from typing import List
import heapq


class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        max_height_diff = []
        sum_height = 0
        for pos, height in enumerate(heights[1:], 1):
            if height > heights[pos - 1]:
                height_diff = height - heights[pos - 1]
                heapq.heappush(max_height_diff, height_diff)
                if len(max_height_diff) > ladders:  # 最多只保存 ladders 个最大值
                    sum_height += heapq.heappop(max_height_diff)
                if sum_height > bricks:  # 无法达到当前位置
                    return pos - 1
        return pos
返回顶部

在手机上阅读