Leetcode题解(3):接雨水

LeetCode42
参考题解

1. 动态规划

        对于任意一个条形块 $height[i]$ ,能蓄水的必要条件是存在 $i > l > 0$ ,$i< r < n$ 使得 $height[l] > height[i]$ 并且 $height[r] > height[i]$ 。当上述条件成立时,这个条形块的蓄水量就等于 $min(height[l],\ height[r]) - height[i]$ 。所以我们可以记录每个条形块对应的左右两边最高的条形块,然后每次遍历时比较左右两边的最高条形块,并取其中较小者。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = height[0];
        right[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++)
            left[i] = Integer.max(height[i], left[i - 1]);
        for (int i = n - 2; i >= 0; i--)
            right[i] = Integer.max(height[i], right[i + 1]);
        int res = 0;
        for (int i = 1; i < n - 1; i++)
            res += (Integer.min(left[i], right[i])) - height[i];
        return res;
    }
}

2. 双指针

        观察上面的 $left[\ ]$ 和 $right[\ ]$ ,可以发现它们元素的状态仅依赖于其左边或者右边元素的状态以及 $height[\ ]$ ,我们可以利用这个特性,将数组优化掉。
        对于每个 $i$ ,只要 $left[i] > height[i]$ ,$right[i] > height[i]$ ,并且 $left[i] < right[i]$ ,那么就由左边条形柱决定蓄水量,否则就由右边决定。也就是说,对于每个 $height[i]$ ,只要其左右两边存在 $left_-max > height[i]$ 并且 $right_-max > height[i]$ 即可蓄水。所以我们可以记录一个 $left_-max$ 和一个 $right_-max$ ,然后利用双指针遍历更新。指针移动规则是:

        采用上述的更新规则后,左右指针中的一个会最终指向最高的条形柱并固定不动。代码实现如下:

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, res = 0, left_max = 0, right_max = 0;
        while (l <= r) {
            if (height[l] < height[r]) {
                if (height[l] > left_max) left_max = height[l];
                else res += left_max - height[l];
                l++;
            } else {
                if (height[r] > right_max) right_max = height[r];
                else res += right_max - height[r];
                r--;
            }
        }
        return res;
    }
}

Leetcode题解(3):接雨水