42. 接雨水 👌难

42. 接雨水

//双指针，最优解法
func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }
    left, right := 0, len(height)-1
    leftmax, rightmax := height[0], height[len(height)-1]
    var res int
    for ;left < right; {
        if rightmax > leftmax {
            res += leftmax - height[left]
            left ++
            if height[left] > leftmax {
                leftmax = height[left]
            }
        } else {
            res += rightmax - height[right]
            right--
            if height[right] > rightmax {
                rightmax = height[right]
            }
        }
    }
    return res
}

双指针 时间O(N) 空间O(1)

在上述的动态规划方法中，我们用二维数组来存储每个柱子左右两侧的最大高度，但我们递推累加每个柱子的储水高度时其实只用到了 dp[i][0]和 dp[i][1] 两个值，因此我们递推的时候只需要用 int leftMax 和 int rightMax 两个变量就行了。
即将上述代码中的递推公式：
res += Math.min(dp[i][0], dp[i][i1]) - height[i];
优化成：
res += Math.min(leftMax, rightMax) - height[i];
注意这里的 leftMax 是从左端开始递推得到的，而 rightMax 是从右端开始递推得到的。
因此遍历每个柱子，累加每个柱子的储水高度时，也需要用 left 和 right 两个指针从两端开始遍历。