How does the greedy approach apply to the Furthest Building You Can Reach problem?

The greedy approach is applied by always trying to use a ladder for larger gaps and using bricks for smaller gaps, ensuring minimal resource consumption for greater reach.

What role does the heap (priority queue) play in solving this problem?

The heap helps track the largest height differences where bricks are used, allowing us to replace the largest brick usage with a ladder when needed, optimizing resource usage.

What are common mistakes to avoid in the Furthest Building You Can Reach problem?

Common mistakes include not using the heap to track brick usage efficiently or failing to prioritize ladders for larger gaps.

How do edge cases affect the solution for this problem?

Edge cases, such as having no resources or starting with an unreachable building, must be handled by early termination or returning 0.

Can the solution for Furthest Building You Can Reach be improved in terms of time complexity?

The current solution, using a heap, is already optimized with a time complexity of O(n log n). Any improvement would likely involve trade-offs in space or complexity.

#1642

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

可以到达的最远建筑

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

数组贪心堆（优先队列）

题目描述

给你一个整数数组 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 <= 10⁵
1 <= heights[i] <= 10⁶
0 <= bricks <= 10⁹
0 <= ladders <= heights.length

lightbulb

解题思路

方法一：贪心 + 优先队列（小根堆）

梯子最好用在高度差较大的地方，因此我们可以将所有的高度差存入优先队列中，每次取出最小的高度差，如果梯子不够用，则用砖块填补，如果砖块不够用，则返回当前位置。

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 heights 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        h = []
        for i, a in enumerate(heights[:-1]):
            b = heights[i + 1]
            d = b - a
            if d > 0:
                heappush(h, d)
                if len(h) > ladders:
                    bricks -= heappop(h)
                    if bricks < 0:
                        return i
        return len(heights) - 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for the candidate's understanding of greedy algorithms and resource optimization.
question_mark
Ensure they are comfortable with heap operations and how it helps in managing resources efficiently.
question_mark
Evaluate if they can handle edge cases effectively, such as when there are no bricks or ladders.

warning

常见陷阱

外企场景

error
Forgetting to use the heap to track and optimize the largest height differences when resources are exhausted.
error
Failing to correctly prioritize ladders over bricks for larger height gaps.
error
Mismanaging edge cases where no resources are available or all buildings are reachable with limited resources.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there were multiple ladders or bricks at specific intervals?
arrow_right_alt
Can the problem be solved with a more straightforward dynamic programming approach?
arrow_right_alt
What if the heights array is reversed, would the solution change?

help

常见问题

外企场景

继续练习

#1648 销售价值减少的颜色球 #1675 数组的最小偏移量 #1606 找到处理最多请求的服务器