Monday, November 25, 2013

LeetCode Problem : Trapping Rain Water

Problem


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!

Code

int trap(int A[], int n) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int l = 0,area = 0;;
    while(l < n - 2){
        int m = l;
        while(m < n - 1 && A[m] > A[m + 1])
            ++m;
        if(m == n - 1)
            break;
        if(l == m){
            ++l;
            continue;
        }
        int r = m,rmax = r;
        while(r < n && A[r] < A[l]){
            if(A[rmax] < A[r])
            rmax = r;
            ++r;
        }
        if(r == n){
            r = rmax;
        }
        int h = min(A[l],A[r]);
        for(int i = l;i <= r;++i)
            area += h - min(A[i],h);
        l = r;
    }
    return area;
}

No comments:

Post a Comment