自学内容网 自学内容网

20240217-您能到达的最远建筑物

题目要求

给你一个整数数组高度,表示建筑物、一些砖块和一些梯子的高度。

您从 0 号楼开始旅程,然后通过使用砖块或梯子移动到下一栋楼。

当从第 i 座建筑移动到第 i+1 座建筑时(以 0 为索引)、

如果当前建筑的高度大于或等于下一栋建筑的高度,则不需要梯子或砖块。
如果当前建筑的高度小于下一栋建筑的高度,则可以使用一个梯子或(h[i+1] - h[i])块砖。
如果以最佳方式使用给定的梯子和砖块,则返回可以到达的最远建筑物索引(0-索引)。

思路

梯子是论个数的,每一个可以无视高度,而砖块则是有限个数,需要足够多的砖块才能够到达下一栋楼。那么这个问题的核心就是,当遇到下一栋楼比当前高时,是选择用梯子还是用砖块?

最基本的想法肯定是,当楼高的差值特别大的时候我们就用梯子,如果比较小我们就尽可能用砖块,梯子留着给高楼用。那么我们应该如何实现这个思路?

如果我们跳出来看,可以都先使用梯子来完成,并且记录梯子跨过的高度,当遇到比之前更大的高度(更需要用梯子来跳过),我们则把之前用梯子跨过的高度换成砖头。

我们可以使用是个最小堆来完成上述思路。

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int i = 0; i < heights.size() -1; ++i) {
            int diff = heights[i+1] - heights[i];
            if (diff > 0) {
                // 首先尝试使用梯子
                if (ladders > 0) {
                    minHeap.push(diff);
                    --ladders;
                } else if (!minHeap.empty() && minHeap.top() < diff && bricks >= minHeap.top()) {
                    // 如果没有梯子了,但堆中有可以用砖块替换的更小的高度差
                    bricks -= minHeap.top(); // 使用砖块替换堆顶的高度差
                    minHeap.pop();
                    minHeap.push(diff); // 将当前高度差使用梯子
                } else if (bricks >= diff) {
                    // 如果堆中没有更小的高度差,直接使用砖块
                    bricks -= diff;
                } else {
                    return i;
                }
            }
        }
        return heights.size() - 1;
    }
};

最小堆(优先队列)

在C++中,priority_queue是一种自动排序的队列,它保证每次取出的元素都是队列中的最大值(或最小值,取决于如何配置)。priority_queue背后的数据结构通常是一个二叉堆,特别是最大堆或最小堆,这使得它能够在插入和移除元素时保持元素的排序状态。

对于priority_queue<int, vector<int>, greater<int>> minHeap;这行代码,我们可以这样理解其各个部分:

  • int: 这是队列中元素的类型,这里我们存储的是整数,代表建筑物之间的高度差。
  • vector<int>: 这是底层容器,用于存储队列中的元素。priority_queue可以使用任何提供随机访问迭代器的容器类型,如vectordeque。默认情况下,priority_queue使用vector作为其底层容器。
  • greater<int>: 这是一个比较函数对象,它决定了队列中元素的排序方式。默认情况下,priority_queue是最大堆,使用less比较函数,这意味着队列顶部总是最大的元素。通过指定greater<int>作为比较函数,我们将priority_queue配置为最小堆,这意味着队列顶部是最小的元素。

时间复杂度

  1. 遍历建筑物: 我们对建筑物数组进行了一次遍历,所以遍历的时间复杂度是O(n),其中n是建筑物的数量。
  2. 操作最小堆:
    • 插入操作 (heapq.heappush()): 每次插入操作的时间复杂度是O(log k),其中k是堆中元素的数量。在最坏的情况下,如果我们需要为每一座建筑使用一个梯子或砖块,那么k可以接近于n
    • 删除操作 (heapq.heappop()): 同样,每次删除操作的时间复杂度也是O(log k)。在最坏的情况下,这也是O(log n)

因此,整体时间复杂度主要取决于这些堆操作。假设在最坏的情况下,我们对每一对建筑都执行了堆操作(无论是插入还是删除),那么总的时间复杂度将是O(n log n)

空间复杂度

  1. 最小堆: 我们使用了一个最小堆来存储用梯子跨过的高度差。在最坏的情况下,如果我们需要记录每一对建筑之间的高度差,那么这个堆的大小也可以接近于n。因此,空间复杂度是O(n)

综上所述,给出的代码示例的时间复杂度是O(n log n),空间复杂度是O(n)


原文地址:https://blog.csdn.net/fuxxu/article/details/136144965

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!