1、题干
给定 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
2、解题
方法一：动态规划，加法转减法思路
对于接雨水这个问题，正向来看，我们需要求出每一个柱子雨水部分的面积，然后累加得到最终的雨水量。
这个思路最容易想到，也能做，但计算相对比较麻烦，需要分别计算出每一个柱子左右两边最大值。然后取其中较小的一个减去当前柱子高度，获取当前柱子的储水量，依次遍历累加获取最终的储水量。这里我们不推荐。
反向来看，柱子的高度已知，我们可以求出当前总面积，在减去每一个柱子的面积，剩下的就是储水量的和。
这个思路就是把加法转化为减法。根据特征可以看出，左边到最高值一定是递增的，最高值到最右边又依次是递减的。
以左边为例，求当前柱子的最终高度，是不是就是左边存在的最大值，把这个最大值提取出来当做公共变量依次求出每一个柱子的最终值。
代码示例：
// 动态规划，加法转减法基础思路
public static int trap(int[] height) {
int sum = 0;
// 1、求出最大元素的下标，可能是多个
int max = Arrays.stream(height).max().getAsInt();
List<Integer> maxIndexList = new ArrayList<>();
for (int i = 0; i < height.length; i++) {
if (height[i]==max){
maxIndexList.add(i);
}
}
// 多个最大值时，最终高度就是max，求取这部分的雨水
if (maxIndexList.size()>1){
for (int i = maxIndexList.get(0)+1; i < maxIndexList.get(maxIndexList.size()-1); i++) {
sum = sum + (max-height[i]);
}
}
// 2、求出最左的递增序列,计算左侧雨水
int leftMaxIndex = maxIndexList.get(0);
int leftmax = height[0];
for (int i = 1; i < leftMaxIndex; i++) { // 最边上的柱子不可能有雨水，从1开始
if (height[i]>leftmax){
leftmax = height[i];
}
sum = sum + (leftmax-height[i]);
}
// 3、求出最右的递减序列,计算左侧雨水
int rightMaxIndex = maxIndexList.get(maxIndexList.size()-1);
int rightmax = height[height.length-1];
for (int i = height.length-2; i > rightMaxIndex; i--) { // 最边上的柱子不可能有雨水，从1开始
if (height[i]>rightmax){
rightmax = height[i];
}
sum = sum + (rightmax-height[i]);
}
return sum;
}
方法二：动态规划，加法转减法思路优化
思路和方法一是一致的，主要用于优化时间复杂度。
从左到右遍历获取最大值数组1，在从右向左获取最大数组2。两者取较小值就是当前柱子的最小高度。
这个方法只需要两次遍历，时间复杂度为O(n)，计算起来效率比方法一要更高。
左侧求解示例图：
如下红色部分为左侧开始遍历得到的结果集。
右侧求解示例图：
如下红色部分为右侧遍历得到的结果集。
两者取最小的部分得到：
代码示例：
// 动态规划，加法转减法基础思路,优化方案
public static int trap(int[] height) {
int sum = 0;
// 1、求出从左到右的最大值序列
int[] maxLeft = new int[height.length];
int maxTemp = 0;
for (int i = 0; i < height.length; i++) {
if (height[i]>maxTemp){
maxTemp = height[i];
}
maxLeft[i] = maxTemp;
}
// 2、反向求出从右到左的最大值序列
int[] maxRight = new int[height.length];
maxTemp = 0;
for (int i = height.length-1; i >= 0; i--) {
if (height[i]>maxTemp){
maxTemp = height[i];
}
maxRight[i] = maxTemp;
}
// 两者最小值减去height就是当前节点的雨水量
for (int i = 0; i < height.length; i++) {
sum = sum + (Math.min(maxRight[i],maxLeft[i]) - height[i]);
}
return sum;
}
方法三：双指针法
这个思路和上面的方法有些类似的。使用双指针分别指向最左和最右，依次求解左和右较小的那一部分获取雨水值，直到指针相遇结束。
代码示例：
public static int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0; // 记录最左和最右已存在的最大值
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
向阳出发，Dare To Be！！！