题目大意：
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=42
解题思路分析：
对于当前柱子正上方能接多少水，取决于它左边的最高柱子高度，以及右边最高柱子高度，两个最高高度的较小值与当前柱子的高度差（高度差必须为正数），即是当前柱子正上方可以接到的水量。
为了求出每个柱子左边的最高柱子高度，我们需要遍历一遍数组，左边第一颗柱子的左边没有其他柱子，因此它左边的最高高度为0，即leftMax[0]=0，对于第二颗柱子，它左边的最高高度等于左边柱子的高度与leftMax[0]的最大值，与此类推，可以得出：
leftMax[i]=max(leftMax[i-1], height[i-1]);
同理，我们也可以得出每颗柱子右边的最大高度为：
rightMax[i]=max(rightMax[i+1], height[i+1]);
接下来，再循环一遍每颗柱子，计算出其leftMax[i]与rightMax[i]的最小值，如果当前柱子高度小于这个最小值，那么当前柱子正上方可以接的雨水为最小值减去当前高度。
实现代码：
public int trap(int[] height) {
// 每颗柱子左边的最大高度
int[] leftMax = new int[height.length];
// 每颗柱子右边的最大高度
int[] rightMax = new int[height.length];
// 计算每颗柱子左边的最大高度
for(int i=1;i<height.length;i++){
leftMax[i]=Math.max(height[i-1], leftMax[i-1]);
}
// 计算每颗柱子右边的最大高度
for(int i=height.length-2;i>=0;i--){
rightMax[i]=Math.max(height[i+1], rightMax[i+1]);
}
// 返回结果
int res=0;
// 由于两边的柱子上方肯定无法接到雨水，从第二颗柱子循环到倒数第二颗柱子
for(int i=1;i<height.length-1;i++){
// 当前柱子左右最大高度的最小值
int h = Math.min(leftMax[i], rightMax[i]);
// 如果当前高度小于最小值，差值即为当前柱子正上方能够接的雨水量
if(h>height[i]) res+= h-height[i];
}
return res;
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 87.94% of Java online submissions for Trapping Rain Water.
Memory Usage: 37.7 MB, less than 95.21% of Java online submissions for Trapping Rain Water.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-42-trapping-rain-water-解题思路分析/