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!
public class Solution { public int trap(int[] A) { // Start typing your Java solution below // DO NOT write main() function if(A.length <3)return 0; int len = A.length; int[] left = new int[len]; int[] right = new int[len]; for(int i=0; i<len;i++){ left[i] = Math.max(A[i], (i== 0 ? 0 :left[i-1])); } for(int i= len-1 ; i>=0; i--){ right[i] = Math.max(A[i], (i == len-1 ? 0 :right[i+1])); } int sum =0; for(int i=1 ; i<len-1;i++){ sum+= Math.min(left[i], right[i])-A[i]; } return sum; }}