【题目】：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [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
【分析】：
对于位置 i，能装下多少水呢？
能装 2 格水。为什么恰好是两格水呢？因为 height[i] 的高度为 0，而这里最多能盛 2 格水，2-0=2。
为什么位置 i 最多能盛 2 格水呢？因为，位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为l_max和r_max；位置 i 最大的水柱高度就是**min(l_max, r_max)**。
更进一步，对于位置 i，能够装的水为：
water[i] = min(
# 左边最高的柱子
max(height[0..i]),
# 右边最高的柱子
max(height[i..end])
) - height[i]
这就是本问题的核心思路，我们可以简单写一个
暴力算法：
/**
* brute force: O(n^2), O(1)
* @param arr
* @return
*/
public static int getMaxWater(int[] arr){
int lMaxHeight = 0;
int rMaxHeight = 0;
int sum = 0;
for(int i=0; i<arr.length; i++){
//左侧最高柱子高度
for(int j=0; j<=i; j++){
lMaxHeight = arr[j] > lMaxHeight ? arr[j] : lMaxHeight;
}
//右侧最高柱子高度
for(int k=i; k<arr.length; k++){
rMaxHeight = arr[k] > rMaxHeight ? arr[k] : rMaxHeight;
}
sum += Math.min(lMaxHeight, rMaxHeight) - arr[i];
}
return sum;
}
有之前的思路，这个解法应该是很直接粗暴的，时间复杂度 O(N^2)，空间复杂度 O(1)。但是很明显这种计算r_max和l_max的方式非常笨拙，一般的优化方法就是记忆化搜索。
记忆化搜索：
之前的暴力解法，不是在每个位置 i 都要计算r_max和l_max吗？我们直接把结果都缓存下来，别傻不拉几的每次都遍历，这时间复杂度不就降下来了嘛。
我们开两个数组r_max和l_max充当备忘录，**l_max[i]**表示位置 i 左边最高的柱子高度，**r_max[i]**表示位置 i 右边最高的柱子高度。预先把这两个数组计算好，避免重复计算：
/**
* 记忆化搜索（MS）：O(n), O(1)
* @param arr
* @return
*/
public static int getBySearchMemory(int[] arr){
int len = arr.length;
int[] lMax = new int[len];
int[] rMax = new int[len];
lMax[0] = arr[0];
rMax[len - 1] = arr[len -1];
int sum = 0;
for(int j=1; j<arr.length; j++){
lMax[j] = Math.max(arr[j], lMax[j-1]);
}
for(int k=len-2; k>=0; k--){
rMax[k] = Math.max(arr[k], rMax[k+1]);
}
for(int i=0; i<len; i++){
sum += Math.min(lMax[i], rMax[i]) - arr[i];
}
return sum;
}
这个优化其实和暴力解法差不多，就是避免了重复计算，把时间复杂度降低为 O(N)，已经是最优了，但是空间复杂度是 O(N)。下面来看一个精妙一些的解法，能够把空间复杂度降低到 O(1)。
双指针解法:
这种解法的思路是完全相同的，但在实现手法上非常巧妙，我们这次也不要用备忘录提前计算了，而是用双指针边走边算，节省下空间复杂度。
public static int getByTwoPointer(int[] arr){
int len = arr.length;
int sum = 0;
int left = 0;
int right = len - 1;
int lMax = arr[0];
int rMax = arr[len -1];
while(left <= right){
lMax = Math.max(arr[left], lMax);
rMax = Math.max(arr[right], rMax);
if(lMax < rMax){
sum += lMax - arr[left];
left++;
}else{
sum += rMax - arr[right];
right--;
}
}
return sum;
}
你看，其中的核心思想和之前一模一样，换汤不换药。但是细心的读者可能会发现次解法还是有点细节差异：
之前的记忆化搜索解法，l_max[i]和r_max[i]代表的是height[0..i]和height[i..end]的最高柱子高度。
但是双指针解法中，l_max和r_max代表的是height[0..left]和height[right..end]的最高柱子高度。比如这段代码：
此时的l_max是left指针左边的最高柱子，但是r_max并不一定是left指针右边最高的柱子，这真的可以得到正确答案吗？
其实这个问题要这么思考，我们只在乎min(l_max, r_max)。对于上图的情况，我们已经知道l_max < r_max了，至于这个r_max是不是右边最大的，不重要，重要的是**height[i]**能够装的水只和**l_max**有关。
对于 l_max > r_max 的情况也是类似的。
这就是接雨水问题的全部内容，希望大家在算法之路上继续精进～
