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可以使用任何提供随机访问迭代器的容器类型，如vector或deque。默认情况下，priority_queue使用vector作为其底层容器。greater<int>: 这是一个比较函数对象，它决定了队列中元素的排序方式。默认情况下，priority_queue是最大堆，使用less比较函数，这意味着队列顶部总是最大的元素。通过指定greater<int>作为比较函数，我们将priority_queue配置为最小堆，这意味着队列顶部是最小的元素。
时间复杂度
- 遍历建筑物: 我们对建筑物数组进行了一次遍历，所以遍历的时间复杂度是
O(n)，其中n是建筑物的数量。 - 操作最小堆:
- 插入操作 (
heapq.heappush()): 每次插入操作的时间复杂度是O(log k)，其中k是堆中元素的数量。在最坏的情况下，如果我们需要为每一座建筑使用一个梯子或砖块，那么k可以接近于n。 - 删除操作 (
heapq.heappop()): 同样，每次删除操作的时间复杂度也是O(log k)。在最坏的情况下，这也是O(log n)。
- 插入操作 (
因此，整体时间复杂度主要取决于这些堆操作。假设在最坏的情况下，我们对每一对建筑都执行了堆操作（无论是插入还是删除），那么总的时间复杂度将是O(n log n)。
空间复杂度
- 最小堆: 我们使用了一个最小堆来存储用梯子跨过的高度差。在最坏的情况下，如果我们需要记录每一对建筑之间的高度差，那么这个堆的大小也可以接近于
n。因此，空间复杂度是O(n)。
综上所述，给出的代码示例的时间复杂度是O(n log n)，空间复杂度是O(n)。
原文地址：https://blog.csdn.net/fuxxu/article/details/136144965
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！