1. 042

trapping-rain-water

2 算法

http://www.cnblogs.com/grandyang/p/4402392.html

• O(N)

3. 代码

class Solution{
public:
    int trap(vector<int>& heigh){
        int maxi=0,peak=0,sum=0;
        int n=heigh.size();
//get the max position
        for(int i=0;i<n;i++)
            if(heigh[maxi]<heigh[i])
                maxi=i;
//first part:forward to maxi
        for(int i=0;i<maxi;i++){
            if(heigh[i]<peak)
                peak=heigh[i];
            else
                sum+=peak-heigh[i];
        }
//second
        peak=0;
        for(int i=n-1;i>maxi;--i){
            if(heigh[i]>peak)
                peak=heigh[i];
            else
                sum+=peak-heigh[i];
        }
        return sum;
     }
};