42. 接雨水 hard

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

示例 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

解题思路

输入：一个整数数组 height

输出：计算出下雨之后可以接多少雨水

本题属于 相向双指针 问题。

我们可以把每一个台阶想象成一个左右高低不同的木桶
木桶的 左侧板高度 就是 前缀最大值
木桶的 右侧板高度 就是 后缀最大值
木桶能装的水 = min(左侧高度, 右侧高度) - 木桶底部高度(柱子高度)

所以我们可以先计算出每个木桶的前缀最大高度 left_max, 以及每个木桶的后缀最大高度 right_max

然后遍历每一个木桶 min(left_max[i], right_max[i]) - height[i] 就是每个木桶能装的水

进阶优化空间

我们可以通过数组来存储每个木桶的左右两端最大高度，也可以用双指针来解决

假如我们遍历到一个木桶时，我们是可以知道左侧高度或者右侧高度其中一个的

假如我们知道当前木桶左侧高度为 left_max
我们虽然不知道当前木桶的右侧高度，但是我们可以知道右指针指向的木桶的最大高度 right_max
当 left_max < right_max 时，当前木桶的能装的水就是 left_max - height[i]
因为就算当前木桶右侧高度是 0，但是更远处还有更高的木桶，所以依然可以装着么多水
右侧也同理，这样我们就可以将空间复杂度优化到 O(1)

代码实现

pythonjavascript

python

class Solution:
    def trap(self, height: List[int]) -> int:
        # 将每个格子都看成一个水桶，水桶的左端就是左侧最大值，右端就是右侧最大值，能装的水就是 水桶的短板 - 水桶底板高度（台阶高度）
        n = len(height)
        if n == 0:
            return 0  # 边界情况处理

        # left_max[i] 表示位置 i 左侧（包括 i）最高的柱子高度
        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(height[i], left_max[i - 1])

        # right_max[i] 表示位置 i 右侧（包括 i）最高的柱子高度
        right_max = [0] * n
        right_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])

        # 遍历每个位置，计算当前位置能存多少水
        total_water = 0
        for i in range(n):
            # 当前格子的水量 = min(左边最高, 右边最高) - 当前高度
            water_level = min(left_max[i], right_max[i])
            trapped = water_level - height[i]
            total_water += trapped

        return total_water

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const n = height.length;
    const leftMax = Array(height.length).fill(0);
    const rightMax = Array(height.length).fill(0);

    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(height[i], leftMax[i - 1]);
    }

    rightMax[n - 1] = height[n - 1];
    for (let j = n - 2; j >= 0; j--) {
        rightMax[j] = Math.max(height[j], rightMax[j + 1]);
    }

    let ans = 0;
    for (let k = 0; k < n; k++) {
        ans += Math.min(leftMax[k], rightMax[k]) - height[k]
    }

    return ans;
};

空间优化版

pythonjavascript

python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        
        # 初始化左右指针和对应的最大高度
        left, right = 0, n - 1
        left_max, right_max = 0, 0
        total_water = 0  # 累计接到的雨水

        # 当左右指针没有相遇时进行遍历
        while left <= right:
            # 维护当前左右两边的最大高度
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            # 谁的最大高度小，谁就先处理
            if left_max < right_max:
                # 此时左边是短板，能接的水 = 左边最大高度 - 当前高度
                total_water += left_max - height[left]
                left += 1
            else:
                # 右边是短板，能接的水 = 右边最大高度 - 当前高度
                total_water += right_max - height[right]
                right -= 1

        return total_water

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let leftMax = 0;
    let rightMax = 0;
    let left = 0;
    let right = height.length - 1;

    let ans = 0;
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (leftMax < rightMax) {
            ans += leftMax - height[left];
            left++;
        } else {
            ans += rightMax - height[right];
            right--;
        }
    }

    return ans;
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n) or O(1)

链接

42 国际版

42 中文版

42. 接雨水 hard ​

解题思路 ​

进阶优化空间 ​

代码实现 ​

空间优化版 ​

复杂度分析 ​

链接 ​