【LC100】No42. 接雨水

题目描述

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

提示：

• n == height.length

• 1 <= n <= 2 * 104

• 0 <= height[i] <= 105

示例

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

链接

思路

取单位为1的竖条缩小问题。对于每个单位竖条，能接多少雨水，取决于它左边的所有高度的最大高度，和它右边的所有高度的最大高度。

单位竖条类似于底为 1 的水桶，左右两边所有高度的最大高度，分别可以作为水桶的左右两个桶板，那么单位竖条能接的水，取决于左右两个桶板中的较小值，然后减去它自身的高度 height[i]。

例如，计算 i 这个单位竖条能接的水，可以先找到下标 0 到 i 的最大高度，和下标 i 到 length-1 的最大高度。根据短板效应，取二者中的最小值，然后减去 height[i]。

解法一：前缀后缀数组

以上，我们可以先从左右两头分别遍历一次，对于 i，记录从左数开头到 i 的最大值，和从右数开头到 i 的最大值。

然后再进行一次遍历，计算每个单位竖条能取到的水。

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (height == null || len == 1) {
            return 0;
        }
        // 从左开始，到i为止的最大的数
        int[] left = new int[len];
        left[0] = height[0];
        for (int i = 1; i < len; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        // 从右开始，到i为止的最大的数
        int[] right = new int[len];
        right[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        // 计算单位竖条能接的雨水
        int res = 0;
        for (int i = 0; i < len; i++) {
            res += Math.min(left[i], right[i]) - height[i];
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

解法二：双指针

总体思路不变，可以继续优化。

我们可以同时判断两个单位竖条，取两个指针，分别指向数组的左右两端。

例如，取 i 竖条和 j 竖条，其中 i < j。把它俩看作两个水桶，i 水桶的能接的水取决于 i 的左桶板和右桶板，j 则取决于 j 的左桶板和右桶板。

和解法一一样的思路，左桶板的最大值取决于左侧所有高度的最大值，右桶板的最大值取决于右侧所有高度的最大值。

因为 i < j，所以 i 的 左桶板最大值必定小于等于 j 的左桶板最大值；同理，i 的右桶板最大值必定大于等于 j 的右桶板最大值。

由于短板效应，计算能接的水需要取左桶板和右桶板中较小值。

因此，在已经计算完左右两侧最大值作为桶板值之后：

当 i 的左桶板 < j 的右桶板时，代表 i 的左桶板 < i 的右桶板（前边已经推出：i 的右桶板 >= j 的右桶板），此时可以计算 i 的接水量，直接用 i 的左桶板值来计算 i 的接水量，计算完成后向右移动左指针。

同理，当 i 的左桶板 > j 的右桶板时，代表 j 的左桶板 > j 的右桶板（前边已经推出：j 的左桶板 >= i 的左桶板），此时可以计算 j 的接水量，用 j 的右桶板计算 j 的接水量，计算完成后向左移动右指针。

综上，我们只使用了 i 的左桶板值和 j 的右桶板，所以我们可以只使用两个变量，leftMax 保存左侧所有高度最大值，rightMax 保存右侧所有高度的最大值，比较二者的大小即可。

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (height == null || len == 1) {
            return 0;
        }
        int res = 0;
        int left = 0, right = len - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                res += leftMax - height[left];
                left++;
            } else {
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)