题目描述：

给定 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 * 10⁴
0 <= height[i] <= 10⁵

题解：

解题思路：

思路一（动态规划）：

1、题目分析，求中间积水处积水的总和
① 想到积水问题我们首先会相到的是短板效应，积水量的多少取决于短板。
② 我们从左往右看，可以找到最高柱子的左侧积水的高度。
③ 从右往左看，可以找到最高柱子右侧积水的高度。
④ 将两侧的积水高度汇总会得到所有的积水高度.

2、解题步骤
① 从左向右看，遍历容器找当前的高度的最大值进行后续的投影。
② 从右往左看，遍历容器找当前的高度的最大值进行后续的投影。
③ 将两次的投影进行重叠，找到全部的积水高度。
④ 通过：积水高度-柱子高度=积水量

3、复杂度分析：
① 时间复杂度：O(N)，从左->右进行投影为O(N)，从右->左进行投影为O(N)。
② 空间复杂度：O(N)，创建了两个数组，记录从左->右的投影和右->左的投影。

思路二（双指针）：

1、题目分析，题目说要计算能接多少雨水，接水的问题我们很快可以想到接水的多少取决于“短的木板”。因两个柱子就可以接雨水，这里我们自然的想到的双指针的方法。

② 假设最左侧的柱子是left，最右侧的柱子是right。
③ 假设height[left]<height[right]， 则积水量取决于left，因为当left和right的区间之内无论有一个比left高的柱子还是更矮的柱子，left右侧紧挨的区域积水量都取决于left。所以我们就有了一个思想，从left和right中矮的柱子开始，从外向内积水。查找到比矮的柱子还高的柱子，这时替换对应的left或者right，直到left=right。

2、具体思路如下：
① 假设最左侧的柱子是left，最右侧的柱子是right。
② 假设height[left]<height[right]， 则积水量取决于left。
③ 因为当left和right的区间之内无论有一个比left高的柱子还是更矮的柱子，left右侧紧挨的区域积水量都取决于left。
④ 所以我们就有了一个思想，从left和right中矮的柱子开始，从外向内积水，此时统计积水量。
⑤ 查找到比矮的柱子还高的柱子，这时替换对应的left或者right，直到left=right。

3、复杂度分析
① 时间复杂度：O(N)，采用双指针只遍历一遍容器。
② 空间复杂度：O(1)，只定义了几个整形的变量。

代码实现

代码实现（思路一（动态规划））：

#include<iostream>
#include<vector>
using namespace std;
int trap2(vector<int>& height) {
	//定义存储答案的变量 
	int ans=0;
	int len=height.size();
	//存放从左向右看的投影 
	vector<int> left_hight(len);
	//定义当前投影的高度，也就是当前最高的柱子 
	int heightmax=0;
	//从左向右看，遍历容器找当前的高度的最大值进行后续的投影 
	for(int i=0;i<len;i++){
		//查找当前最大高度柱子 
		if(height[i]>heightmax){
			heightmax=height[i];
		}
		//保存每个位置的投影 
		left_hight[i]=heightmax;
	}
	//存放从右向左看的投影
	vector<int> right_hight(len);
	heightmax=0; 
	for(int i=len-1;i>=0;i--){
		if(height[i]>heightmax){
			heightmax=height[i];
		}
		right_hight[i]=heightmax;
		//在记录从右向左的投影时，同时计算积水量 
		ans+=min(left_hight[i],right_hight[i])-height[i];
	}
	
	return ans; 
}

int main(){
	vector<int> height={0,1,0,2,1,0,1,3,2,1,2,1};
	cout<<trap2(height);
	return 0;
}

代码实现（思路二（双指针））：

#include<iostream>
#include<vector>
using namespace std;
int trap1(vector<int>& height) {
	//创建双指针，和存储结果的变量 
	int left=0,right=height.size()-1,ans=0;
	//leftmax和rightmax用于记录从外向内左右两侧最长的边 
	int leftmax=height[left],rightmax=height[right];
	
	while(left<right){	
		//左侧柱子大于右侧，则右侧柱子为短板积水 
		if(height[left]>height[right]){ 
			//注意right--;不能放在这里，因移动得首先判断left<right 
			//如果当前柱子比短板柱子还小则积水  
			if(height[right]<rightmax){
				ans+=rightmax-height[right];
			//如果当前柱子比短板柱子还大则替换短板柱子 
			}else{
				rightmax=height[right];
			}
			--right;
		//右侧柱子大于左侧,则左侧柱子为短板积水
		}else{
			//如果当前柱子比短板柱子还小则积水
			if(height[left]<leftmax){
				ans+=leftmax-height[left];
			//如果当前柱子比短板柱子还大则替换短板柱子
			}else{
				leftmax=height[left];
			}
			++left;
		}
	}
    return ans; 
}
int main(){
	vector<int> height={0,1,0,2,1,0,1,3,2,1,2,1};
	cout<<trap1(height);
	return 0;
} 

代码实现（思路二（双指针另一种写法））：

//因移动的是短板，当left==right时，ans增加0
class Solution2 {
public:
    int trap(vector<int>& height) {
        // 初始化左指针和右指针
        int left = 0, right = height.size() - 1;
        
        // 初始化左右两边的最大高度，分别从左边和右边开始
        int leftMax = height[0], rightMax = height[right];
        
        // 存储积水的总量
        int ans = 0;
        
        // 当左指针小于右指针时，继续向中间收敛
        while (left < right) {
            // 如果左边的高度小于右边的高度
            if (height[left] < height[right]) {
                // 左指针向右移动
                left++;
                // 更新左边的最大高度
                leftMax = max(leftMax, height[left]);
                // 计算当前位置能够积水的数量并加到答案中
                ans += leftMax - height[left];
            } else {
                // 如果右边的高度小于等于左边的高度，右指针向左移动
                right--;
                // 更新右边的最大高度
                rightMax = max(rightMax, height[right]);
                // 计算当前位置能够积水的数量并加到答案中
                ans += rightMax - height[right];
            }
        }
        
        // 返回最终的积水总量
        return ans;
    }
};

LeetCode 热题 100_接雨水(7_42)原题链接
欢迎大家和我沟通交流(✿◠‿◠)