Trapping Rain Water

浏览数：18 / 时间：2015年06月11日

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!

思路：

1.先把最左边的0去掉；

2.挨个遍历每个柱子。

3.去重的处理

代码：

class Solution{
public:
    int trap(int A[], int n) {
        if(A==NULL||n==0) return 0;
        int i;
        int res=0;
        for(i=0;i<n;++i){
            if(A[i]!=0) break;
        }
        int start=i+1;
        map<int,bool> repeatNum;
        while (start<n)
        {
            if(repeatNum.count(start)){++start;continue;}
            int l;int r;
            for(l=start-1;l>=0;--l){
                if(A[l]>A[start]){
                    break;
                }
            }
            for (r=start+1;r<n;++r)
            {
                if(A[r]==A[start]) repeatNum[r]=true;
                if(A[r]>A[start]){
                    break;
                }
            }
            if(l==-1||r==n){
                ++start;continue;
            }
            int temp=(min(A[l],A[r])-A[start])*(r-l-1);
            res+=temp;
            ++start;
        }
        
        return res;
    }
};