力扣第42题 接雨水

前言

记录一下刷题历程 力扣第42题 接雨水

---

接雨水

原题目：给定 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

分析

我们首先可以想到的就是统计一列左边和右边所有柱子的最高高度，根据下图我们可以知道左右最高高度较低的值与当前柱子的高度差就是这一列能存储的水的高度。这是第一种方法但是需要O(n)的空间复杂度，有没有优化空间呢，我们来看方法2.

第二种方法，我们其实并不需要同时计算左右两边的最高高度，假如说我们对于当前列已经知道了左侧的最高高度，只要右侧出现比左侧高度还要高，那么左侧的最高高度就一定是水体的顶部，然后我们可以计算该列的水体高度，我们从数组两端向中间遍历，分别计算左指针和左侧最高高度，右指针和右侧最高高度，找到对应结果较低的那一列直接更新结果即可

代码如下：

第一种方法：

class Solution {
public:// 接收一个整数数组 height，表示每个柱子的高度，返回可以接住的雨水总量int trap(vector<int>& height) {// n 表示柱子的总数int n = height.size();// res 用于存储最终结果，也就是可以接住的雨水总量int res = 0;// 创建两个数组，分别存储每个位置的左边最高柱子和右边最高柱子vector<int> leftMax(n);  // leftMax[i] 表示位置 i 左边最高的柱子vector<int> rightMax(n); // rightMax[i] 表示位置 i 右边最高的柱子// 初始化 leftMax 数组的第一个元素，因为第 0 个位置没有左边的柱子，所以 leftMax[0] 就是 height[0]leftMax[0] = height[0];// 计算每个位置的左边最高柱子，从左到右遍历for(int i = 1; i < n - 1; i++) {// leftMax[i] 是当前位置 i 和位置 i-1 的最高柱子之间的较大值leftMax[i] = max(leftMax[i - 1], height[i]);}// 初始化 rightMax 数组的最后一个元素，因为最后一个位置没有右边的柱子，所以 rightMax[n-1] 就是 height[n-1]rightMax[n - 1] = height[n - 1];// 计算每个位置的右边最高柱子，从右到左遍历for(int i = n - 2; i > 0; i--) {// rightMax[i] 是当前位置 i 和位置 i+1 的最高柱子之间的较大值rightMax[i] = max(rightMax[i + 1], height[i]);}// 遍历每个柱子，计算该柱子上方能够接住的雨水for(int i = 1; i < n - 1; i++) {// 当前位置的雨水容量等于左边和右边最高柱子之间的较小值减去当前柱子的高度int capacity = min(leftMax[i], rightMax[i]) - height[i];// 累加结果，capacity 是该位置能接住的水res += capacity;}// 返回最终的接水量return res;}
};

第二种方法：

class Solution {
public:int trap(vector<int>& height) {// 获取柱子的总数int n = height.size();// 如果柱子数小于3，无法接住雨水，直接返回0if (n < 3) return 0;// 结果变量，用于存储接住的雨水总量int res = 0;// 左指针初始化为数组的起始位置int left = 0;// 右指针初始化为数组的结束位置int right = n - 1;// 左边最大值初始化为0int leftMax = 0;// 右边最大值初始化为0int rightMax = 0;// 双指针遍历，直到两个指针重合while (left < right) {// 更新左边最大值leftMax = max(leftMax, height[left]);// 更新右边最大值rightMax = max(rightMax, height[right]);// 如果左边最大值小于右边最大值，处理左边的情况if (leftMax < rightMax) {// 当前位置的水量 = 左边最大值 - 当前柱子的高度res += leftMax - height[left];// 左指针向右移动left++;} // 如果右边最大值小于等于左边最大值，处理右边的情况else {// 当前位置的水量 = 右边最大值 - 当前柱子的高度res += rightMax - height[right];// 右指针向左移动right--;}}// 返回接住的雨水总量return res;}
};

代码解释

第一种方法主要思路：

1.对于每个柱子而言，能接住的水量取决于左边最高的柱子和右边最高的柱子，以及当前位置柱子的高度。柱子能接住的水量是左、右柱子中较矮的那个减去当前柱子的高度。

为了快速得到每个柱子左边和右边的最大值，我们通过预处理分别计算 leftMax 和 rightMax 数组。然后对于每个柱子，计算它上方可以接住的水量并累加到结果中。

2.首先，我们用两个数组 leftMax 和 rightMax 分别记录每个柱子左边和右边的最高柱子。

leftMax[i] 表示位置 i 左边的最高柱子，包括 i 本身。
rightMax[i] 表示位置 i 右边的最高柱子，包括 i 本身。

3.遍历 height 数组计算每个位置的左边最高值和右边最高值。

对于每个位置的柱子，我们计算其能接住的雨水量：min(leftMax[i], rightMax[i]) - height[i]。
累加每个位置的水量得到最终结果。

复杂度分析：

时间复杂度：该算法需要遍历三次数组，时间复杂度为 O(n)。
空间复杂度：需要额外的两个数组存储左边和右边的最大值，空间复杂度为 O(n)。
这就是该算法的基本思路和实现方式。

第二种方法主要思路：

1.初始化：

获取 height 数组的大小 n，存储在变量 n 中。
如果柱子的数量小于3（例如0、1或2个柱子），无法形成凹槽来接雨水，直接返回0。
初始化结果变量 res 为0，用于存储计算得到的雨水总量。
初始化两个指针 left 和 right 分别指向数组的起始和结束位置。
初始化 leftMax 和 rightMax 为0，用于记录当前左边和右边的最大高度。

2.双指针遍历：

当 left 指针小于 right 指针时进行循环。
在每次循环中：
更新 leftMax 为当前位置左指针所指柱子的高度与之前 leftMax 的最大值之间的较大值。
更新 rightMax 为当前位置右指针所指柱子的高度与之前 rightMax 的最大值之间的较大值。

如果 leftMax 小于 rightMax，说明左边的最高柱子更矮，处理左边的情况：

计算当前位置可以接住的雨水量，等于 leftMax 减去当前柱子的高度。
将该雨水量累加到结果变量 res 中。
将左指针向右移动一位。

否则，说明右边的最高柱子更矮或相等，处理右边的情况：

计算当前位置可以接住的雨水量，等于 rightMax 减去当前柱子的高度。
将该雨水量累加到结果变量 res 中。
将右指针向左移动一位。

3.返回结果：

循环结束后，返回最终计算得到的接水总量 res。

复杂度分析

时间复杂度：该算法的时间复杂度为 O(n)，因为每个柱子位置在循环中只会被访问一次。
空间复杂度：该算法的空间复杂度为 O(1)，仅使用了常量级的额外空间，不需要额外的数组。
这个双指针方法在时间复杂度和空间复杂度上都具有较好的性能，是处理这个问题的一种高效解法。