Trapping Rain Water
给一个数组, 里面的数字代表bar的高度, 求这些bar能圈住多少面积水. 这个题其实很难, 不是看答案真不会.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class Solution { public int trap(int[] height) { if(height.length == 0 || height == null) return 0; int max = 0; int maxIndex = -1; for(int i = 0 ; i < height.length; i++){ if(height[i] > max){ max = height[i]; maxIndex = i; } } int pre = 0; int sum = 0; for(int i = 0; i < maxIndex ; i++) { if(height[i] > pre){ sum += (height[i] - pre) * (maxIndex - i); pre = height[i]; } sum -= height[i]; } pre = 0; for(int i = height.length - 1; i > maxIndex; i--) { if(height[i] > pre){ sum += (height[i]-pre) * (i - maxIndex); pre = height[i]; } sum -= height[i]; } return sum; } } |