42. Trapping Rain Water

题目描述：

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.

Example 1:

Input:[0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
![Image text](http://www.leetcode.com/static/images/problemset/rainwatertrap.png)
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!

Note:

1. Suppose negative integers is not palindrome

题目翻译

给定n个非负整数，它们用来表示每栏宽度为一的地图的海拔，计算下雨后能够存储多少水

示例1：

输入： [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
![Image text](http://www.leetcode.com/static/images/problemset/rainwatertrap.png)
上面的地图是由array[0 1 0、2、1,0,1,3,2,1,2,1]组成。在这种情况下,下雨后我们能存储6单位的水（蓝色部分）。感谢马科斯贡献这张照片!

注意： NULL

解题方案

标签： Two Pointers

思路：

• 基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，
• 可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。
• 这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。
• 这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。

代码：

int trap(int* height, int heightSize) {
    int *L = height, *R = L+heightSize-1, level = 0, water = 0;
    while (L < R) {
        int lower = *L < *R ? *L++ : *R--;
        if (lower > level) level = lower;
        water += level - lower;
    }
    return water;
}

参考资料

• http://blog.csdn.net/linhuanmars/article/details/20888505
• 作者：段静