@@ -0,0 +1,1478 @@
+// 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%0A%0Apublic class Solution %7B%0A%09// brute force search. O(n2) %0A  //   public int trap(int%5B%5D A) %7B%0A%09%09// int len = A.length;%0A%0A%09%09// if(len == 0) return 0;%0A%0A%09%09// int water = 0;%0A%0A%0A%09%09// // %5B4,2,3%5D%0A%09%09// for(int i = 1; i %3C len - 1; i++)%7B%0A%09%09// %09int current = A%5Bi%5D;%0A%09%09// %09int left = -1;%0A%09%09// %09int right = -1;%0A%0A%09%09// %09for(int l = i - 1; l %3E= 0; l--)%7B%0A%09%09// %09%09if(A%5Bl%5D %3E current)%7B%0A%09%09// %09%09%09left = left %3E A%5Bl%5D? left : A%5Bl%5D;%0A%09%09// %09%09%7D%0A%09%09// %09%7D%0A%0A%09%09// %09if(left == -1) continue;%0A%0A%09%09// %09for(int r = i + 1; r %3C len; r++)%7B%0A%09%09// %09%09if(A%5Br%5D %3E current)%7B%0A%09%09// %09%09%09right = right %3E A%5Br%5D? right : A%5Br%5D;%0A%09%09// %09%09%7D%0A%09%09// %09%7D%0A%0A%09%09// %09if(right == -1) continue;%0A%0A%09%09// %09water += (Math.min(left, right) - current);%0A%09%09// %7D%0A%0A%09%09// return water;%0A  //   %7D%0A%0A%09// dp approach, O(n)%0A%09public int trap(int%5B%5D A) %7B%0A%09%09int len = A.length;%0A%0A%09%09if( len == 0 ) return len;%0A%0A%09%09int%5B%5D leftMax = new int%5Blen%5D;%0A%0A%09%09int tempMax = A%5B0%5D;%0A%09%09leftMax%5B0%5D = tempMax;%0A%0A%09%09for(int i = 1; i %3C len - 1; i++)%7B%0A%09%09%09tempMax = Math.max(tempMax, A%5Bi - 1%5D);%0A%09%09%09leftMax%5Bi%5D = tempMax;%0A%09%09%7D%0A%0A%09%09int water = 0;%0A%09%09int right = A%5Blen - 1%5D;%0A%0A%09%09for(int i = len - 2; i %3E= 0; i--)%7B%0A%09%09%09int left = leftMax%5Bi%5D;%0A%09%09%09right = Math.max(right, A%5Bi + 1%5D);%0A%0A%09%09%09int lower = left %3E right? right : left;%0A%0A%09%09%09if(lower %3E A%5Bi%5D)%7B%0A%09%09%09%09water += (lower - A%5Bi%5D);%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09return water;%0A%09%7D%0A%7D

add trapping rain water solution