Question

1642. 可以到达的最远建筑

English Version

题目描述

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

解法

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

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

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

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

class Solution {
  public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    int n = heights.length;
    for (int i = 0; i < n - 1; ++i) {
      int a = heights[i], b = heights[i + 1];
      int d = b - a;
      if (d > 0) {
        q.offer(d);
        if (q.size() > ladders) {
          bricks -= q.poll();
          if (bricks < 0) {
            return i;
          }
        }
      }
    }
    return n - 1;
  }
}

class Solution {
public:
  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<int>> q;
    int n = heights.size();
    for (int i = 0; i < n - 1; ++i) {
      int a = heights[i], b = heights[i + 1];
      int d = b - a;
      if (d > 0) {
        q.push(d);
        if (q.size() > ladders) {
          bricks -= q.top();
          q.pop();
          if (bricks < 0) {
            return i;
          }
        }
      }
    }
    return n - 1;
  }
};

func furthestBuilding(heights []int, bricks int, ladders int) int {
  q := hp{}
  n := len(heights)
  for i, a := range heights[:n-1] {
    b := heights[i+1]
    d := b - a
    if d > 0 {
      heap.Push(&q, d)
      if q.Len() > ladders {
        bricks -= heap.Pop(&q).(int)
        if bricks < 0 {
          return i
        }
      }
    }
  }
  return n - 1
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}