Trapping Rain Water
给一个数组, 里面的数字代表bar的高度, 求这些bar能圈住多少面积水. 这个题其实很难, 不是看答案真不会.
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;
}
}