leetcode42. 接雨水

方法：按列计算加上动态规划存储最大值
具体来说每个节点（列）能存的水等于它左边的最大值和右边的最大值里较小的一个减去自身。
动态规划的思路：为了减少查找次数我们先把从左到右，和从右到左每个节点的左右最大值分别记录在左右两个数组里。
因为我们知道从左往右左边第一个节点的最大值是自身，从右往左右边的第一个节点的最大值也是自身。即：递推式

def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        res = 0
        l = [height[0]] + [0]*(n-1)
        r = [0]*(n-1) + [height[n-1]]
        for i in range(1,n):
            l[i] = max(l[i-1],height[i])
        for i in range(n-2,-1,-1):
            r[i] = max(r[i+1],height[i])
        for i in range(1,n-1):
            res += max(0, min(l[i-1],r[i+1])-height[i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

双指针代替计算左右最大值，同时开始就行，一定有一边的最大值较小，说明当前柱子最多水的高度就是那么多，之后再减去柱子自身高度.

def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        l,r = 0,len(height)-1
        lmax,rmax = 0,0
        while l < r:
            lmax = max(height[l],lmax)   #左右同时开始，肯定有一边的最大值比较低
            rmax = max(height[r],rmax)
            if lmax < rmax:              #低的那个最大值那边开始计算，因为这个是可以确定的较小的最大值
                ans += lmax - height[l]
                l += 1
            else:
                ans += rmax - height[r]
                r -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

差不多的动态规划思路进行简化

def trap(height):
    """
    :type height: List[int]
    :rtype: int
    """
    ans = 0
    h1 = 0
    h2 = 0
    for i in range(len(height)):
        h1 = max(h1, height[i])
        h2 = max(h2, height[-i - 1])
        ans = ans + h1 + h2 - height[i]  # 从左到右的最大值加上从右到左的最大值减去全局最大值就是两边较小的最大值，较小的最大值减去自身长度就是当前节点接水数
    return ans - len(height) * h2  # 因为遍历完要减去左右两边较高的那个
1
2
3
4
5
6
7
8
9
10
11
12
13