LeetCode - Trapping Rain Water | Darren's Blog

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.

public int trap(int[] A) {

        if (A == null || A.length == 0)

            return 0;

        int n = A.length;

        // Used to record the maximum height to the left and the right of each bar

        int[] maxHeights = new int[n];

        // Scan from left to right, find the maximum height to the left of each bar

        int maxHeight = 0;

        for (int i = 0; i < n; i++) {

            maxHeights[i] = maxHeight;

            maxHeight = Math.max(maxHeight, A[i]);

        }

        // Scan from right to left, find the maximum height to the right of each bar

        // The minimum of them is the height of the water (if any) on the bar

        // The difference between the height of the water and that of the bar is the

        // volume of the water on that bar

        maxHeight = 0;

        int volume = 0;     // Accumulated volume of water

        for (int i = n-1; i >= 0; i--) {

            maxHeights[i] = Math.min(maxHeight, maxHeights[i]);

            maxHeight = Math.max(maxHeight, A[i]);

            if (maxHeights[i] > A[i])       // Has water on the bar

                volume += maxHeights[i] - A[i];     // Accumulate the volume of the water

        }

 

        return volume;

    }

Code from http://yucoding.blogspot.com/2013/05/leetcode-question-111-trapping-rain.html

int trap(int A[], int n) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (n<2){return 0;}   

         

        int *l = new int[n];

        int *r = new int[n];

         

        int water =0;

         

        l[0]=0;

        for (int i=1;i<n;i++){

            l[i]= max(l[i-1], A[i-1]);

        }

                 

        r[n-1] = 0;

        for (int i=n-2;i>=0;i--){

            r[i]=max(r[i+1],A[i+1]);

        }

         

        for (int i=0;i<n;i++){

            if (min(l[i],r[i])-A[i] >0 ){

                water += min(l[i],r[i])-A[i];

            }

        }

         

        return water;

         

    }

Code from https://coderwall.com/p/outcbg
先计算柱状图的凸包面积，然后减去柱状图本身的面积，就是所能存储水的多少。时间复杂度：O(n)，空间复杂度：O(1)。
int trap(int A[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if(n<=2) return 0; int sum=A[0],mi=0; for(int i=1;i<n;i++) { sum+=A[i]; if(A[i]>A[mi]) mi=i; } int left=0,right=0,min=0; for(int i=1;i<=mi;i++) if(A[i]>=A[min]) { left+=A[min]*(i-min); min=i; } min=n-1; for(int j=n-2;j>=mi;j--) if(A[j]>=A[min]) { right+=A[min]*(min-j); min=j; } return left+right+A[mi]-sum; }
Read full article from LeetCode - Trapping Rain Water | Darren's Blog