Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return 6. 
The above elevation map 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. Thanks Marcos for contributing this image!
【题目分析】
题目给出一个整数序列代表高度图，要求计算下雨后图中的积水量。
【思路】
我们只要找到高度图中的凹陷部分，然后把所有凹陷的容积加起来即可。那么如何找到这些凹陷部分呢？
有这样一个想法：给定高度图两端的高度，那些比这两端都低的部分肯定会形成凹陷，如果是相等则不形成凹陷，如果比当前高度高，则我们要重新确定高度图的两端高度。这个过程如下：
1. 初始两端最低高度high = 0， 容量capacity = 0；
2. height[begin] <= high，不形成凹陷，begin++；
3. height[begin] > high； height[end] > high；high = min(height[begin], height[end])； 因此high = 1；
此时height[begin] == high，height[end] == high；所以begin++，end--；
4. height[begin] < high；形成凹陷，capacity += high - height[begin]；此时capacity = 1；begin++；
5. height[begin] > high； height[end] > high；high = min(height[begin], height[end])； 因此high = 2；
此时height[begin] == high，height[end] == high；所以begin++，end--；
6. height[begin] < high；形成凹陷，capacity += high - height[begin]；此时capacity = 2；begin++；
height[end] < high；形成凹陷，capacity += high - height[begin]；此时capacity = 3；end--；
7. height[begin] < high；形成凹陷，capacity += high - height[begin]；此时capacity = 5；begin++；
height[end] = high；不形成凹陷；end--；
7. height[begin] < high；形成凹陷，capacity += high - height[begin]；此时capacity = 6；begin++；
8. 返回最大容量6；
【java代码】
1 public class Solution { 2 public int trap(int[] height) { 3 if(height == null || height.length <= 2) return 0; 4 5 int sum = 0, maxhigh = 0; 6 int begin = 0, end = height.length-1; 7 while(begin <= end){ 8 if(height[begin] < maxhigh){ 9 sum += maxhigh - height[begin++];10 }11 else if(height[end] < maxhigh){12 sum += maxhigh - height[end--];13 }14 else{15 maxhigh = Math.min(height[begin], height[end]);16 if(height[begin] <= maxhigh) begin++;17 if(height[end] <= maxhigh) end--;18 }19 }20 return sum;21 }22 } 