[LeetCode] Trapping Rain Water

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!

class Solution {
public:
    int trap(int A[], int n) {
        int preIndex = 0,postIndex = 0;
        int result = 0,cur=0;
        int flag = 1;
        while(flag == 1){
            flag = 0;
            for(int i=1;i<n-1;){
                preIndex = i-1;
                cur = A[i];
                i++;
                while(i<n-1 && A[i]==cur)
                    i++;
                postIndex = i;
                if(A[postIndex]>cur && A[preIndex]>cur){
                    int h = min(A[postIndex],A[preIndex])-cur;
                    for(int j = preIndex+1;j<postIndex;j++){
                         result += h;
                         A[j] += h;
                    }
                        
                    i = postIndex+1;
                    flag = 1;
                }    
            }//end for
        }//end while
        return result;
    }//end func
};
原文地址:https://www.cnblogs.com/Xylophone/p/3924824.html