FlareBall's Blog
0%

42.接雨水

Posted on Edited on In ,

前后缀最大值

对于位置 $i$ 而言，它最终能接多少雨水，取决于它左侧最高柱子和右侧最高柱子中较矮的那个，减去当前位置柱子高度。因为水位不可能超过两侧挡板中的短板。

因此可以预处理每个位置右侧的最高柱子高度，再在遍历数组时维护左侧最高柱子高度，这样就能在 $O(1)$ 时间内计算当前位置的积水量。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int trap(int[] height) {
        int ans = 0, n = height.length;
        int[] suf = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = Math.max(suf[i + 1], height[i + 1]);  // 位置i右侧最高的高度
        }
        int pre = 0;  // 位置i左侧最高的高度
        for (int i = 0; i < n; ++i) {
            ans += Math.max(Math.min(pre, suf[i]) - height[i], 0);
            pre = Math.max(pre, height[i]);
        }
        return ans;
    }
}

双指针

也可以进一步优化空间。

接雨水的本质仍然是看当前位置两侧最大值中的较小者。设左右指针分别为 $left$ 和 $right$，同时维护左侧最大值 $pre$ 与右侧最大值 $suf$。

如果 $pre < suf$，说明此时左侧当前位置能接多少水已经可以确定，只由 $pre$ 决定；因为右侧一定存在一个不小于 $suf$ 的挡板，它比 $pre$ 更高，短板就是 $pre$。同理，如果 $pre \ge suf$，则右侧当前位置能接多少水已经可以确定，只由 $suf$ 决定。

这样每次只结算较矮一侧即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int trap(int[] height) {
        int ans = 0, suf = 0, pre = 0, left = 0, right = height.length - 1;
        while (left < right) {
            pre = Math.max(pre, height[left]);
            suf = Math.max(suf, height[right]);
            if (pre < suf) {
                ans += pre - height[left];
                left++;
            } else {
                ans += suf - height[right];
                right--;
            }
        }
        return ans;
    }
}