"RainWater = WholeArea - Blocks"


  • -1
    N

    As it depicted in the image:

    The size of the "RainWater (the blue area)" is equal to the size of the "WholeArea (the blue area + the black area)" minus the size of the "Blocks (the black area)".

    int trap(int A[], int n) {
        int wholeArea = 0, blocks = 0, left = 0, right = n - 1, height = 0;
        while(left <= right) {
            if(min(A[left], A[right]) > height) {
                wholeArea += (right - left + 1) * (min(A[left], A[right]) - height);
                height = min(A[left], A[right]);
            }
            blocks += (A[left] < A[right]) ? A[left++] : A[right--];
        }
        return wholeArea - blocks;
    }

  • 0
    A

    the problem is how to calculate the whole area, we know that the black area is the sum of the array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.