题目描述

给定一个整数数组 heights，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始）时：

• 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块。
• 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个 砖块。
• 如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始）。

样例

输入：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 ，因为没有更多砖块或梯子。

输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7

输入：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

(贪心，二分答案) $O(n \log n)$

1. 二分可以到达的最远距离。
2. 假设当前的距离为 pos，求出 [0, pos] 中所有爬升的高度差，存到数组 d 中。显然需要让较大的 latters 个高度差使用梯子。
3. 通过 nth_element 函数做部分排序，求出第 d.size() - ladders 大的位置（下标从 0 开始），其左侧位置的高度都小于等于该位置。
4. 累加小于 d.size() - ladders 所有位置的高度差，求出需要砖块的数量并判断。

时间复杂度

• 二分的范围为 $0$ 到 $n-1$。
• nth_element 的时间复杂度为 $O(n)$，所以判断一次的时间复杂度就是 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储临时高度差数组。

C++ 代码

class Solution {
private:
    bool check(int pos, const vector<int> &heights, int bricks, int ladders) {
        vector<int> d;
        for (int i = 1; i <= pos; i++)
            if (heights[i] > heights[i - 1])
                d.push_back(heights[i] - heights[i - 1]);

        if (ladders >= d.size())
            return true;

        nth_element(d.begin(), d.begin() + (d.size() - ladders), d.end());

        for (int i = 0; i < d.size() - ladders; i++) {
            if (bricks < d[i]) return false;
            bricks -= d[i];
        }
        return true;
    }

public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        const int n = heights.size();
        int l = 0, r = n - 1;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid + 1, heights, bricks, ladders)) l = mid + 1;
            else r = mid;
        }

        return l;
    }
};

算法2

(贪心，小跟堆) $O(n \log n)$

1. 显然，在一段旅程中，需要将梯子用在差距较大的楼层之间。
2. 此时，这个问题就变成了求动态前 $k$ 大，梯子的个数就是 $k$。前 $k$ 大的高度差使用梯子，剩余的高度差使用砖块。
3. 维护一个小跟堆，每次需要爬升时，先使用梯子。
4. 如果梯子不够用了，从判断当前的高度差是否大于小根堆的堆顶。如果大于，则用砖块替换小跟堆的堆顶所使用的梯子，当前新的高度差使用梯子；否则当前新的高度差使用砖块。
5. 使用砖块时，判断一下砖块是否够用。

时间复杂度

• 每个位置最多插入、删除和查询一次小跟堆，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储小跟堆。

C++ 代码

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        const int n = heights.size();
        priority_queue<int, vector<int>, greater<int>> q;

        for (int i = 1; i < n; i++) {
            if (heights[i] <= heights[i - 1]) continue;
            int d = heights[i] - heights[i - 1];
            if (ladders > 0) {
                ladders--;
                q.push(d);
            } else {
                if (!q.empty() && d > q.top()) {
                    if (bricks < q.top())
                        return i - 1;
                    bricks -= q.top();
                    q.pop();
                    q.push(d);
                } else {
                    if (bricks < d)
                        return i - 1;
                    bricks -= d;
                }
            }
        }

        return n - 1;
    }
};