LeetCoder-Trapping Rain Water

Trapping Rain Water
题目解析：
给定一个大小为n的非负整数集合，代表一个容器。容器的宽度(bar)为1，计算这个容器可以存储多少水。

思路：
计算每一个bar可以存储的容量，相加就是总的容量。每一个bar的容量取决于其左右两侧的最小高度，因此分别从头及尾遍历此数组，计算每一个Bar其左右两侧的最大高度。最后遍历数组，根据本身高度及左右两侧高度计算每一个bar的容量。

代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> high_r;
        vector<int> high_l;
        int max=0;
        int res = 0;
        for (int i=0;i<height.size();++i){
            if (i==0){
                high_l.push_back(max);
                continue;
            }
            if (max < height[i-1]){
                max = height[i-1];
                
            }
            high_l.push_back(max);
        }
        max = 0;
        for (int i=height.size()-1;i>=0;--i){
            if (i==height.size()-1){
                high_r.push_back(max);
                continue;
            }
            if (max < height[i+1]){
                max = height[i+1];
                
            }
            high_r.push_back(max);
        }
        int len = height.size()-1;
        //reverse(high_l.begin(),high_l.end());
        for (int i = 0;i<height.size();++i){
            int high = high_r[len-i]>high_l[i]? high_l[i]:high_r[len-i];
            //cout<<"index: "<<i<<"; High: "<<high<<","<<endl;
            
            if (high>=height[i]){
                res += high-height[i];
            }
        }
        
        return res;
    }
};