42. Trapping Rain Water

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.

image

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

我的解法

一开始我有一个错误的解法，这个解法是通过有穷自动机分析出来的；虽然这这种解法最终无法实现，但我发现有穷自动机真的是个逻辑分析的好工具，也算增长了经验

• 先遍历一遍找出最大值，并假设一开始每一列都有着max高度的水；这个是个 O(N)的操作；
• 而后从上至下，逐行地减去头和尾溢出的部分，这是个kO(N)的操作，k取决于最大的高度能有多大
• 总结来说这是一个O(kN)的操作

func trap(height []int) int {
    
    if len(height) == 0{
        return 0;
    }
    
    // fill with the max;
    max := height[0]
    for _, val := range height {
        if max < val {
            max = val
        }
    }
    result := max * len(height)
    
    // delete the first 0 cols
    sp := 0
    for ; sp < len(height) && height[sp] == 0; sp++ {
        result -= max;
    }
    
    // delete the existing places
    for e:=sp; e<len(height); e++{
        result -= height[e];
    }
    
    // delete row by row
    for curH := max; curH >= 1; curH-- {
        
        // delete the head
        for e := sp;; e++ {
            if height[e] < curH {
                result--;
            } else{
                break;
            }
        }
        // delete the tail
        for e := len(height)-1;;e--{
            if height[e] < curH{
                result--;
            } else{
                break;
            }
        }
    }
    return result;
}

更巧妙的

讨论区里利用双指针，可以有 O(N)（只遍历一遍）的算法。具体看这里，这里不说详细的解析，简单来说就是左右同步扫描，并将水从低处往高处逐列填。这里只贴一下代码

class Solution {
public:
    int trap(int A[], int n) {
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }
};

更多的解法

Solution有更多的解法，还有一种动态规划的解法很有意思，将左边加起来，右边加起来，重叠部分就是所求。