当前位置：首页 > news >正文

LeetCode 算法：接雨水c++

news 来源：原创 2024/9/29 4:37:07

原题链接🔗：接雨水
难度：困难⭐️⭐️⭐️

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
在这里插入图片描述
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 10⁵

题解

双指针法

题解:

LeetCode 上的“接雨水”问题是一个典型的双指针问题，它要求我们计算在给定的条形图中，能够接住的雨水量。
这个问题可以通过以下步骤解决：

理解问题：首先，我们需要理解雨水是如何被接住的。雨水只能被两个更高的条形所夹住。因此，问题转化为找到所有可能的“容器”，这些容器的两侧条形的高度差即为能够接住的雨水量。

初始化：我们需要两个指针，分别指向数组的两端，即 left 和 right。同时，我们需要两个变量来记录从 left 到 right 遍历过程中遇到的左侧和右侧的最大高度，即 leftMax 和 rightMax。

遍历数组：使用一个循环，当 left 小于 right 时，执行以下操作：

如果 height[left] 小于 height[right]，则移动 left 指针。此时，左侧条形的高度决定了雨水的量。如果
height[left] 小于 leftMax，则更新 leftMax。
如果 height[left] 大于或等于 leftMax，则当前位置可以接住雨水，其量为 leftMax - height[left]。
同理，如果 height[left] 大于 height[right]，则移动 right 指针，并更新 rightMax。如果 height[right] 小于
rightMax，则当前位置可以接住雨水，其量为 rightMax - height[right]。

更新结果：在每一步中，如果当前位置可以接住雨水，则将计算出的雨水量累加到总结果 ans 中。

继续移动：更新完当前位置的雨水量后，根据 height[left] 和 height[right] 的比较结果，移动 left 或
right 指针，继续寻找下一个可以接住雨水的位置。

结束循环：当 left 和 right 相遇时，循环结束。

返回结果：返回计算出的总雨水量 ans。

复杂度：时间复杂度O(N)，空间复杂度O(1)。
代码过程：

trap 函数接受一个整数数组 height 作为输入，返回能够接住的雨水量。

函数首先检查数组是否为空，如果是，则返回0。

使用两个指针 left 和 right 分别从数组的两端开始向中间移动。

使用两个变量 leftMax 和 rightMax 来记录从左到右和从右到左遍历时遇到的最大高度。

在每一步中，比较 height[left] 和 height[right]：

如果 height[left] 小于 height[right]，则移动 left 指针，并且如果 height[left] 小于 leftMax，则更新 leftMax。
否则，计算当前位置能够接住的雨水量，并累加到 ans。
类似地，如果 height[left] 大于或等于 height[right]，则移动 right 指针，并且更新 rightMax。

重复上述步骤直到 left 和 right 相遇。

main 函数提供了两个示例数组 height1 和 height2，调用 trap 函数，并打印出能够接住的雨水量。

c++ demo：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 函数用于计算接雨水的量
int trap(vector<int>& height) {int n = height.size();if (n == 0) return 0;// 初始化左右边界的最大高度int leftMax = 0, rightMax = 0;int left = 0, right = n - 1;int ans = 0;// 双指针从两端向中间移动while (left < right) {if (height[left] < height[right]) {// 如果左侧的条形高度小于右侧if (height[left] >= leftMax) {// 更新左侧的最大高度leftMax = height[left];}else {// 计算雨水量ans += leftMax - height[left];}left++;}else {// 右侧的条形高度不小于左侧if (height[right] >= rightMax) {// 更新右侧的最大高度rightMax = height[right];}else {// 计算雨水量ans += rightMax - height[right];}right--;}}return ans;
}int main() {// 示例输入vector<int> height1 = { 0,1,0,2,1,0,1,3,2,1,2,1 };vector<int> height2 = { 4,2,0,3,2,5 };// 调用 trap 函数并打印结果cout << "Rainwater trapped by height1: " << trap(height1) << endl;cout << "Rainwater trapped by height2: " << trap(height2) << endl;return 0;
}