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 int res = 0 ; if(A.length < 3) return res; int[] left = new int[A.length -2]; int[] right = new int[A.length -2]; for(int i = 0 ; i < A.length -2; i++){ left[i] = i > 0 ? Math.max(left[i-1],A[i]):A[i];//current pos - 1 } for(int i = A.length -3; i>= 0 ; i--){ right[i] = i <A.length-3 ? Math.max(right[i+1], A[i+2]):A[i+2];//current pos +1 } for(int i = 0 ; i < A.length -2; i++){ int temp = Math.min(left[i],right[i]); if(temp > A[i+1]) res += temp - A[i+1]; } return res; } }
public class Solution { public int trap(int[] A) { if(A.length < 3) return 0; int[] left = new int[A.length]; int[] right = new int[A.length]; left[0] = A[0]; for(int i=1; i<A.length; i++){ left[i] = Math.max(left[i-1], A[i]); } right[A.length-1] = A[A.length-1]; for(int i=A.length-2; i>=0; i--){ right[i] = Math.max(right[i+1], A[i]); } int sum = 0; for(int i=1; i<A.length-1; i++){ sum += Math.min(left[i], right[i]) - A[i]; } return sum; } }
learned: 挨个分析每个A[i]能trapped water的容量，然后将所有的A[i]的trapped water容量相加即可; 其次，对于每个A[i]能trapped water的容量，取决于A[i]左右两边的高度（可延展）较小值与A[i]的差值，即volume[i] = [min(left[i], right[i]) - A[i]] * 1，这里的1是宽度，如果the width of each bar is 2,那就要乘以2了