42. Trapping Rain Water - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为two pointers。 注意到water的面积可以通过water和block的总面积减去block的面积得到。 总面积可以看到是大致以最高的那个block为中心分布的。

因此可以采用双指针逐步向最高点靠近。 左右指针较低的那个为limit，若为当前的高度curLevel，则(r-l+1)*(curLevel-level)肯定在总面积中。

public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int l = 0, r = height.length-1;
        int level = 0;
        int all = 0, block = 0;
        while(l <= r) {
            int curLevel = Math.min(height[l], height[r]);
            if(curLevel > level) {
                all += (r - l + 1) * (curLevel - level);
                level = curLevel;
            }
            if(height[l] < height[r]) {
                block += height[l++];
            } else {
                block += height[r--];
            }
        }
        return all - block;
    }
}