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.

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!
Tripping Rain Water

解题思路:
首先寻找到数组中的局部极小点, 然后以该极小点为中心向左(left)右(right)两边扩张窗口, 当窗口达到最大时计算窗口之间的容积. 然后重新寻找局部极小点, 重复以上过程.

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;
        
        int left = 0, right = 0;
        int sum = 0;
        
        for(int i = 1; i < height.size() - 1; ++i) {
            // 寻找局部极小点
            if(height[i-1] <= height[i] || height[i] > height[i+1]) 
                continue;
            // 寻找极小点的左边边界
            for(left = i-1; left > 0; left--) {
                if(height[left] > height[left-1])
                    break;
            }
            // 寻找极小点的右边边界
            right = i + 1;
            for(int j = i + 1; j < height.size(); ++j) {
                if(height[j] >= height[right]) {
                    right = j;
                    if(height[right] > height[left]) 
                        break;
                }
            }
            // 计算左右边界之间的容量
            int level = min(height[left], height[right]);
            for(int j = left+1; j < right; ++j) {
                if(level > height[j])
                    sum += (level - height[j]);
            }
            // 更新索引值, 为下一个局部极小点做准备
            i = right; 
        }
        return sum;
    }
};