42. Trapping Rain Water --H ！！！！！老毛病，第一个方法不太对

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

A:

[解题思路]
对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
3. 再扫描一遍，求取容积并加和。

Mistakes:

****************扫两遍***************************

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n<=2)
            return 0;
        vector<int> maxLeft(n,0);
        for(int i = 1;i<n;i++){
            maxLeft[i] = max(maxLeft[i-1], height[i-1]);
        }
        int res = 0;
        int maxRight = height[n-1];
        for(int i = n-2;i>0;i--){
            res += max(0, (min(maxLeft[i], maxRight) - height[i]));
            maxRight = max(maxRight, height[i]);
        }
        return res;
    }
};

Learned:
1： 尽量让自己的helper function 为private 。 阿三可能用这个来据你。