题目介绍
这道题挺有意思的，给定一个非负数的每个宽度为 1 的柱形图，问你下雨天能接多少雨水。例题中给定的数组能接的总数为 6，即图中蓝色部分。
题目分析
我们先来随便举个例子吧。例如示例中给出的数组第 6 位（也就是索引位置 5）高度为 0，此时这个位置能盛的水是 2。这个 2 是咋么算出来的呢。从当前位置往它的左边查找，查出最高的水位，即索引 3 (值为 2)。从当前位置往右边找出它的最高位，即索引位置 7 (值为 3)，然后取他们中的最小值高度 min (2,3) 减去当前位置的高度 (0)=2。为什么取的是两者的最小值呢。很简单的道理，两边之间能盛的水的高度必然会和其中一边高度持平的，再高就溢出了。
代码实现
/** * @param Integer[] $height * @return Integer */ function trap($height) { $res = 0; $size = count($height); for ($i = 1; $i < $size - 1; $i++) { $left = 0; $right = 0; for ($j = $i; $j >= 0; $j--) { $left = max($left, $height[$j]); } for ($j = $i; $j < $size; $j++) { $right = max($right, $height[$j]); } $res += min($left, $right) - $height[$i]; } return $res; }
你应该已经发现了，上面的执行时间是 O (n*n)。每一个位置我们都遍历查找了左右两边，仅仅是为了找最大值，我们为什么不把每个位置左右两边最大值一次存起来？
/** * @param Integer[] $height * @return Integer */ function trap($height) { $res = 0; $size = count($height); $left[0] = $height[0]; for ($i = 1; $i < $size; $i++) { $left[$i] = max($left[$i - 1], $height[$i]); } $right[$size - 1] = $height[$size - 1]; for ($i = $size - 2; $i >= 0; $i--) { $right[$i] = max($right[$i + 1], $height[$i]); } for ($i = 1; $i < $size - 1; $i++) { $res += min($left[$i], $right[$i]) - $height[$i]; } return $res; }
其实上面的解题思路就是一个动态规划的过程。动态规划最重要的两步：1 是状态的定义，即上面的这两个定义:
$left[0] = $height[0]; $right[$size - 1] = $height[$size - 1];
第二步就是状态转移方程，即上面的
$left[$i] = max($left[$i - 1], $height[$i]); $right[$i] = max($right[$i + 1], $height[$i]);
其实动态规划就像是开启了上帝的视角，每次都能获取到全局的情况。经常用来解最优，最近，最少这类题目。你再进一步分析，好像动态规划的思想就是一个空间换时间的方案。第一个解的时间是 O (n 的平方)，空间就一个变量 O (1)。再来看第二道解，时间是 O (n)，空间是 O (n)。本质上来说就是空间换时间的方案。最后其实这道题还有其他能解的方案。。。。刷着刷着，乐趣就上来了。
