力扣HOT100：T.42 接雨水｜辅助数组法or双指针法算法实现笔记及打卡（12/100）

【力扣hot100】【LeetCode 42】接雨水｜辅助数组法or双指针法

给定 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] <= 105

1. 辅助数组法（暴力解法）

如图实例1所示，最大接水量为6。

例如，下标为4的区域，柱子高度为1，而其左侧最高高度为2（下标3），其右侧最高高度为3（下标7），水不可能比最低的柱子还要高（木桶效应），故下标4的接水量为水高-柱高 = 2 – 1 = 1；

再例如，下标为5的区域，柱高为0，而其左侧最高高度为2（下标3），其右侧最高高度为3（下标7），同样的原理，故下标5的接水量为水高-柱高 = 2 – 0 = 2.

依次类推，不妨得到

water[i] = min(left_max[i] – right_max[i]) – height[i];

*思路：*从左到右，从右到左，依次遍历，找每个位置找左右最大值

*时间/空间复杂度：*O(n)、O(n)

参考代码如下

#include <vector>
#include <algorithm> // 用于max/min函数

using namespace std;

class Solution {
public:
int trap(vector<int>& height) {
// 至少需要3个元素才能形成凹陷接水
if (height.size() < 3) {
return 0;
}

int n = height.size();
vector<int> left_max(n, 0); // 存储每个位置左侧的最大高度
vector<int> right_max(n, 0); // 存储每个位置右侧的最大高度
int ans = 0; //接水量

// 第一步：填充left_max数组
for (int i = 1; i < n; ++i) {
left_max[i] = max(left_max[i-1], height[i-1]);
}

// 第二步：填充right_max数组
for (int i = n – 2; i >= 0; –i) {
right_max[i] = max(right_max[i+1], height[i+1]);
}

// 第三步：计算总接水量
for (int i = 0; i < n; ++i) {
// 当前位置能接的水量 = 左右最大高度的较小值 – 自身高度（非负）
int current_water = min(left_max[i], right_max[i]) – height[i];
ans += max(current_water, 0); // 避免负数累加
}

return ans;
}
};

1.2 双指针法（优化解法）

不必每次都重新找左右最大值，通过双指针（left 从左、right 从右）遍历数组，用 pre_max 记录左指针遍历过的最大高度，sub_max 记录右指针遍历过的最大高度，每次选择 pre_max 和 sub_max 较小的一侧计算接水量，最终累加得到总接水量，

时间复杂度 O (n)，空间复杂度 O (1)。

class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
int left = 0, right = height.size() – 1; //左、右指针
int pre_max = 0, sub_max = 0; //前缀和后缀的最大值
while (left <= right){
pre_max = max(pre_max, height[left]); //找前缀最大值
sub_max = max(sub_max, height[right]); //找后缀最大值
if (pre_max < sub_max){
ans += pre_max – height[left]; //更新最大接水容量
left += 1;
}else{
ans += sub_max – height[right]; //更新最大接水容量
right -= 1;
}
}
return ans;

}
};

辅助数组法图：B站@波波微课