题目

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;

     }

};