回到顶部暗色模式

Leetcode题解（3）：接雨水

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$ ，然后利用双指针遍历更新。指针移动规则是：

如果 $height[l] < height[r]$ ，则移动左指针；
否则，移动右指针。

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

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）：接雨水

回到顶部