算法之接雨水

给定 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

思路： 先找出 可以构成左低右高 的区域获得能存的雨水的量， 然后处理 左高右低 的部分（将这部分反过来发现， 可以构成 至少 一个 左高右低 的区域）

	class Solution {
        public int trap(int[] height) {
            if (height == null || height.length <= 2) {
                return 0;
            }
            int left = 0;
            int right = left + 1;
            int res = 0;
            int maxPos = left;
            //正向
            while (right < height.length ) {
                if (height[right] >= height[left]) {
                    maxPos = right;
                    res += sum(height, left, right);
                    left = right;
                    right += 1;
                    continue;
                }
                right++;
            }
            //反向
            right = height.length - 1;
            left = right -1;
            while (left >= 0 && left >= maxPos){
                if (height[left] >= height[right]) {
                    res += reverseSum(height, left, right);
                    right = left;
                    left -= 1;
                    continue;
                }
                left --;
            }

            return res;
        }

        private int reverseSum(int[] height, int left, int right) {
            int sum = 0;
            for (int i = right - 1; i > left; i--){
                sum += height[right] - height[i];
            }
            return sum;
        }

        private int sum(int[] height, int left, int right) {
            int sum = 0;
            for (int i = left + 1; i < right; i++){
                sum += height[left] - height[i];
            }
            return sum;
        }
    }