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
由于没有更多砖块或梯子，无法继续前进。

示例 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^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

解题思路

这是一道经典的贪心算法问题，核心思想是用梯子应对最大的高度差。

解题思路

我们可以使用**小根堆（优先队列）**来维护需要使用梯子的最大的几个高度差：

  1. 贪心策略：梯子应该用在高度差最大的地方，因为梯子可以跨越任意高度，而砖块的消耗与高度差成正比
  2. 动态调整：使用小根堆维护当前使用梯子的所有高度差，堆的大小不超过梯子数量
  3. 处理流程：
    • 遍历建筑物，计算每次需要向上爬的高度差
    • 如果高度差为正（需要向上爬），先假设用梯子
    • 将高度差加入小根堆，如果堆大小超过梯子数量，弹出最小值用砖块代替
    • 检查砖块是否足够，不够则返回当前位置

这种方法的精髓在于延迟决策：我们先假设都用梯子，当梯子不够时，将最小的高度差改为用砖块，这样保证了梯子总是用在最需要的地方。

时间复杂度：O(n log k)，其中 k 是梯子数量 空间复杂度：O(k)，堆的最大大小为梯子数量

代码实现

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆
        int n = heights.size();
        
        for (int i = 0; i < n - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff > 0) {
                minHeap.push(diff);
                if (minHeap.size() > ladders) {
                    bricks -= minHeap.top();
                    minHeap.pop();
                    if (bricks < 0) {
                        return i;
                    }
                }
            }
        }
        
        return n - 1;
    }
};

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        import heapq
        
        min_heap = []  # 小根堆
        n = len(heights)
        
        for i in range(n - 1):
            diff = heights[i + 1] - heights[i]
            if diff > 0:
                heapq.heappush(min_heap, diff)
                if len(min_heap) > ladders:
                    bricks -= heapq.heappop(min_heap)
                    if bricks < 0:
                        return i
        
        return n - 1

public class Solution {
    public int FurthestBuilding(int[] heights, int bricks, int ladders) {
        var minHeap = new PriorityQueue<int, int>();
        int n = heights.Length;
        
        for (int i = 0; i < n - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff > 0) {
                minHeap.Enqueue(diff, diff);
                if (minHeap.Count > ladders) {
                    bricks -= minHeap.Dequeue();
                    if (bricks < 0) {
                        return i;
                    }
                }
            }
        }
        
        return n - 1;
    }
}

var furthestBuilding = function(heights, bricks, ladders) {
    const minHeap = new MinPriorityQueue();
    
    for (let i = 0; i < heights.length - 1; i++) {
        const diff = heights[i + 1] - heights[i];
        
        if (diff <= 0) continue;
        
        minHeap.enqueue(diff);
        
        if (minHeap.size() > ladders) {
            const minDiff = minHeap.dequeue().element;
            bricks -= minDiff;
            
            if (bricks < 0) {
                return i;
            }
        }
    }
    
    return heights.length - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log k)，其中 n 是建筑数量，k 是梯子数量
空间复杂度O(k)，用于存储堆中的元素

相关题目