题目描述：
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.
解题思路：
思路一：开辟两个数组空间，逐个遍历数组，找出该位置左边的最大值与右边的最大值，分别放到两个数组中。然后对整个数组进行遍历，位置装水后的值不能超过该位置左右最高值中的最小数。该算法需三次遍历数组，但是时间复杂度为O(n)；空间需开辟两个数组空间，空间复杂度为O(n)。
代码如下：
public class Solution {
public int trap(int[] height) {
int length;
int maxLeftHeight = 0, maxRightHeight = 0;
int result = 0;
int temp;
if (height == null || (length = height.length) == 0)
return 0;
int[] leftMaxHeight = new int[length];
int[] rightMaxHeight = new int[length];
for (int i = 0; i < length; i++) {
leftMaxHeight[i] = maxLeftHeight;
maxLeftHeight = Math.max(maxLeftHeight, height[i]);
}
for (int i = length - 1; i >= 0; i--) {
rightMaxHeight[i] = maxRightHeight;
maxRightHeight = Math.max(maxRightHeight, height[i]);
}
for (int i = 0; i < length; i++) {
temp = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
if (temp >= height[i])
result += temp - height[i];
}
return result;
}
}
思路二：
设置两个指示变量，分别存放当前指向的两个位置。找出左位置的左边的最高值和右位置的右边的最高值。对于两者中的最小值，表明当前位置加上水过后的值不超出该值，那么相减即可，反之，对另一个相减。该算法只需要一次遍历数组，所以效率更高，时间复杂度为O(n);空间方面不需要开辟数组空间，所以为常数空间。
代码如下：
public class Solution {
public int trap(int[] height) {
int length;
int left, right;
int maxLeftHeight = 0, maxRightHeight = 0;// 记录当前位置左边， 右边的最大值
int result = 0;
if (height == null || (length = height.length) == 0)
return 0;
left = 0;
right = length - 1;
while (left < right) {
maxLeftHeight = Math.max(maxLeftHeight, height[left]);
maxRightHeight = Math.max(maxRightHeight, height[right]);
if (maxLeftHeight < maxRightHeight) {
result += maxLeftHeight - height[left];
left++;
} else {
result += maxRightHeight - height[right];
right--;
}
}
return result;
}
}
Java [Leetcode 42]Trapping Rain Water
原文：http://www.cnblogs.com/zihaowang/p/5027379.html