@@ -0,0 +1,1566 @@
+/***%0A * 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.%0A *%0A * For example, %0A * Given %5B0,1,0,2,1,0,1,3,2,1,2,1%5D, return 6.%0A */%0Apublic class Solution %7B%0A    // Solution 1: O(n)%0A    /*%0A    public int trap(int%5B%5D A) %7B%0A        int n = A.length;%0A        int max_left%5B%5D = new int %5Bn%5D;%0A        int max_right%5B%5D = new int%5Bn%5D;%0A        // find left max and right max %0A        // water stored in a single bar is equal to%0A        // Min(right_max, left_max) - bar_val%0A        for (int i = 1; i %3C n; i++) %7B%0A            max_left%5Bi%5D = Math.max(max_left%5Bi - 1%5D, A%5Bi - 1%5D);%0A            max_right%5Bn - i - 1%5D = Math.max(max_right%5Bn - i%5D, A%5Bn - i%5D);%0A        %7D%0A        int sum = 0;%0A        for (int i = 0; i %3C n; i++) %7B%0A            int height = Math.min(max_left%5Bi%5D, max_right%5Bi%5D);%0A            if (height %3E A%5Bi%5D)%0A                sum += height - A%5Bi%5D;%0A        %7D%0A        return sum;%0A    %7D%0A    */%0A%0A    // Solution 2: O(n) O(1)%0A    // Find max value index%0A    // Then calculate the right part and left part separately.%0A    public int trap(int%5B%5D A) %7B%0A        int imax = 0;%0A        int n = A.length;%0A        for (int i = 0; i %3C n; i++)%0A            if (A%5Bi%5D %3E A%5Bimax%5D) imax = i;%0A%0A        int water = 0;%0A        for ( int i = 0, peak = 0; i %3C imax; i++)%0A            if (A%5Bi%5D %3E peak) peak = A%5Bi%5D;%0A            else water += peak - A%5Bi%5D;%0A        for (int i = n - 1, top = 0; i %3E imax; i--)%0A            if (A%5Bi%5D %3E top) top = A%5Bi%5D;%0A            else water += top - A%5Bi%5D;%0A%0A        return water;%0A    %7D%0A%7D%0A

add TrappingRainWater.java