layout: article
title: 接雨水

接雨水

原题链接：42. 接雨水 - 力扣（LeetCode）

动态规划重点思路：

首先用两个数组，lmax [i] 代表第 i 列左边最高的墙的高度，rmax[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的）

对于 lmax我们其实可以这样求。

lmax[i] = Max(lmax[i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。

对于 rmax我们可以这样求。

rmax[i] = Max(rmax[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。