给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 左右两边是漏的，就是第一个柱子和最后一个柱子不接雨水。

暴力递归

class Solution {/*** @param Integer[] $height* @return Integer*/function trap($height) {$n = count($height);$ans = 0;for ($i = 1; $i < $n - 1; $i++) {$l_max = 0;$r_max = 0;// 找右边最高的柱子for ($j = $i; $j < $n; $j++)$r_max = max($r_max, $height[$j]);// 找左边最高的柱子for ($j = $i; $j >= 0; $j--)$l_max = max($l_max, $height[$j]);// 如果自己就是最高的话，// l_max == r_max == height[i]$ans += min($l_max, $r_max) - $height[$i];}return $ans;}
}

直接爆内存。

双指针

class Solution {/*** @param Integer[] $height* @return Integer*/function trap($height){$n = count($height);if (!$n) return 0;$l = 0;$l_max = $height[$l];$r = $n - 1;$r_max = $height[$r];$ans = 0;while ($l < $r) {if ($height[$l] < $height[$r]) {if ($height[$l] < $l_max) $ans += $l_max - $height[$l];else $l_max = $height[$l];$l++;} else {if ($height[$r] < $r_max) $ans += $r_max-$height[$r];else $r_max = $height[$r];$r--;}}return $ans;}
}

拿left指针做实例

如果大于if ($height[$l] < $l_max)

最终数量会加上当前最大的减掉$l指针指着的，$ans += $l_max - $height[$l];