2019-12-19 吴亲库里 库里的深夜食堂
这道题挺有意思的,给定一个非负数的每个宽度为 1 的柱形图,问你下雨天能接多少雨水。例题中给定的数组能接的总数为 6,即图中蓝色部分。
![](https://github.com/wuqinqiang/Lettcode-php/raw/master/images/42.png)
我们先来随便举个例子吧。例如示例中给出的数组第 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)。本质上来说就是空间换时间的方案。最后其实这道题还有其他能解的方案。。。。刷着刷着,乐趣就上来了。
![](https://github.com/wuqinqiang/Lettcode-php/raw/master/qrcode_for_gh_c194f9d4cdb1_430.jpg)