題目：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
image.png
解題思路：從頭到尾掃描數(shù)組，找到兩個(gè)數(shù)蛉迹，使得這兩個(gè)數(shù)中間的所有數(shù)都小于等于這兩個(gè)數(shù)敢艰，相當(dāng)于是找到兩個(gè)最高的矩形飒炎，然后計(jì)算這兩個(gè)矩形中間的水的面積诡曙，然后疊加起來臀叙。Java代碼：
public class Solution {
public int trap(int[] height) {
int sum = 0;
int startPosition = 0;
int index = 0;
int endHeight = 0;
int endPosition = 0;
// 定位到第一個(gè)非0的位置
while (startPosition < height.length && height[startPosition] == 0) {
++startPosition;
}
while (startPosition < height.length - 1) {
index = startPosition + 1;
endPosition = index;
endHeight = height[endPosition];
while (index < height.length) {
if (height[startPosition] > height[index]) {
if (height[index] >= endHeight) {
endPosition = index;
endHeight = height[endPosition];
}
++index;
} else {
endPosition = index;
endHeight = height[endPosition];
break;
}
}
sum += calculateTrapRain(height, startPosition, endPosition);
startPosition = endPosition;
}
return sum;
}
private int calculateTrapRain(int[] height, int start, int end) {
int lowerHeight = Math.min(height[start], height[end]);
int sum = 0;
for (int i = start + 1; i < end; ++i) {
sum += (lowerHeight - height[i]);
}
return sum;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] height = new int[] {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(solution.trap(height));
}
}
