算法leetcode

【堆贪心】力扣1642-可以到达的最远建筑

字数统计: 869字   |   阅读时长: 3分
, , ,

摘要: 一个堆贪心的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

题目

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

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

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

  • 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
  • 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

提示：

1
2
3
4
1 <= heights.length <= 1e5
1 <= heights[i] <= 1e6
0 <= bricks <= 1e9
0 <= ladders <= heights.length

示例 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

题解

算法：贪心、堆

假设当前走一步要提升的高度差为 diff，对于梯子来说，1 个梯子即可；对于砖块来说，需要 diff 个砖块。如果梯子没了，砖块也少于 diff 个，则当前这一步就走不了了，最远就能走到当前文章。

考虑从 0 走到位置 i 的过程，其中有些位置用了砖块，有些位置用了梯子。如果我们想把某个梯子换成砖块，应该尽量选择高度差最小的那一步把梯子换成砖块。

因此向前走的过程中，可以优先使用梯子，梯子没了，就取过往用梯子走过的高度差中最小的高度差换为用砖块，砖块不够则无法前进。

过程中可以用堆来维护【过往用梯子走过的高度差中最长的高度差】，使用梯子走某个高度差的时候，将该高度差压堆；将过往用梯子的最小高度差改为用砖块时，将堆顶弹出。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int n = heights.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < n - 1; ++i)
        {
            int diff = heights[i + 1] - heights[i];
            if(diff <= 0)
                continue;
            if(ladders > 0)
            {
                --ladders;
                pq.push(diff);
            }
            else
            {
                pq.push(diff);
                if(pq.top() <= bricks)
                {
                    bricks -= pq.top();
                    pq.pop();
                }
                else
                    return i;
            }
        }
        return n - 1;
    }
};
Share