LeetCode 42. 接雨水 - PHP

给定 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];