Trapping Rain Water
This is a simple problem. At each index i
, let left[i]
be the higest bar on its left
and right[i]
be the highest bar on its right, then the depth of water at this position
equals to max(left[i], right[i]) - height[i]
. Note the depth of water must not be negative,
so if height[i]
is greater than the highest possible top edge of water(max(left[i], right[i]
),
we count it as zero.
public class TrappingRainWater {
public int trap(int[] height) {
if (height.length == 0) return 0;
int[] left = new int[height.length];
int[] right = new int[height.length];
for (int i = 1; i < left.length; i++) {
left[i] = Math.max(height[i - 1], left[i - 1]);
}
for (int i = right.length - 2; i >= 0; i--) {
right[i] = Math.max(height[i + 1], right[i + 1]);
}
int sum = 0;
for (int i = 0; i < height.length; i++) {
sum += Math.max(0, Math.min(left[i], right[i]) - height[i]);
}
return sum;
}
}