1. 题目描述
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
为了方便理解，还是决定给大家翻译一下吧：
给定n个非负整数，表示一个高度图，其中每个条形的宽度为1，计算从上往下下雨后它能集聚多少水。
2. 示例
示例1：
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
什么意思呢？通过一个图我们就明白了，大概是这样：
图中黑色的表示高度数组值，蓝色的表示集聚的雨水，一个方格代表1，故集聚了6个单位的雨水。
示例2：
同理：
Input: height = [4,2,0,3,2,5]
Output: 9
图示这样：黄色为高度值，蓝色为雨水量。
3. 输入要求
n == height.length0 <= n <= 3 * 1040 <= height[i] <= 105- 复杂度要求为O(n)
4. 题目解析
有人看到示例2会觉得，咦？是不是可以用面积来计算呢？
但是又看到示例1的时候，会发现，面积并不是特别方便，因为，并不是中间所有的间隙都能够储存雨水。只有形成“凹”字型时，才能够集聚雨水。
所以我们只能另辟蹊径。
我们使用多指针法：假设数组为A[length];
因为要求复杂度为O(N)，故需要遍历一遍，故分别设置 left 和 right 两个指针。并使用while(left<right)来控制循环。
其实，我们从示例1中这张图就可以看出：如果我们设置一个中间变量 Max 用来表示当前遇到的最大值，那么，在遍历高度数组A时，下一个数组值 A[left] 如果比 Max 小，则用Max减去该值就是此处可以存储的雨水量，且更新 left 继续遍历；如果该值 A[left] 大于 Max 时，那么 Max 更新为 A[left]，且更新 left 指针，继续遍历。
代码如：
if(A[left]>=Max){ Max = A[left]; }else{ res += (Max-A[left]); } left++;
但是，我们这里要考虑的不仅仅是一面，因为会存在这样一种情况就是：
输入为：[5,0,0,0,0,0]
输出不是5*5=25，而是0，因为右侧没有高度，形成不了“凹”字型。
所以我们应该还需要设置右侧最大值，为了与前面的最大值Max做区分，我们将前述的最大值 Max 改为 leftMax，此处右侧最大高度值为rightMax，这样我们就可以从两侧向中间收缩。
判断到底当前步是从左还是从右收缩，需要依据 A[left] 和 A[right] 的值的大小——【谁小谁收缩】
右侧代码为：
if(A[right]>=rightMax){ rightMax = A[right]; }else{ res += (Max-A[right]); } right--;
故：整体过程就是：
public int trap(int[] A){ int res = 0; int left = 0; int right = A.length-1; int leftMax = 0; //左侧海拔最高值 int rightMax = 0; //右侧海拔最高值 while(left<right){ if(A[left]<=A[right]){ //左右两侧谁矮收缩谁 if(A[left]>=leftMax){ leftMax = A[left]; //更新左侧海拔最高值 }else{ res += (leftMax-A[left]); //累计雨水量 } left++; //更新左侧指针 }else{ if(A[right]>=rightMax){ rightMax = A[right]; //更新右侧海拔最高值 }else{ res += (rightMax-A[right]); //累计雨水量 } right--; //更新右侧指针 } } }
参考及致谢：
1、LeetCode Top 100 高频算法题42. Trapping Rain Water：来自《菜鸟名企梦》公众号，希望大家关注一波，谢谢~~~
Over...