42. Trapping Rain Water

NO IMAGE

題目:
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.

解答:

public class Solution {
public int trap(int[] height) {
//左邊比右邊小或者大都可以盛水,所以我們不能直接確定右邊是否會有一個柱子比較大,能盛所有現在積攢的水。
//那麼我們就找到中間最大的那個柱子,把它分成左右兩邊,那麼不管從左邊還是右邊都能保證最後可以有最高的柱子在,之前盛的水都是有效的
if (height.length <= 2) return 0;
int maxHeight = 0, maxIndex = 0;
int result = 0;
//find the max height and its index
for (int i = 0; i < height.length; i  ) {
if (height[i] > maxHeight) {
maxHeight = height[i];
maxIndex = i;
}
}
//left part
int maxLeft = height[0];
for (int i = 1; i < maxIndex; i  ) {
if (height[i] > maxLeft) {
maxLeft = height[i];
} else {
result  = maxLeft - height[i];
}
}
//right part
int maxRight = height[height.length - 1];
for (int i = height.length - 2; i > maxIndex; i--) {
if (height[i] > maxRight) {
maxRight = height[i];
} else {
result  = maxRight - height[i];
}
}
return result;
}
}