42. 接雨水

Origin: LeetCode 42

题目描述

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

示例

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6

Input: height = [4, 2, 0, 3, 2, 5] Output: 9

约束

• 1 <= height.length <= 3 × 10
• 0 <= height[i] <= 10

关键信息

• 每根柱子上能接的水 = min(左边最高, 右边最高) - 当前高度
• 双指针 O(n) 或 预处理左右最大值数组 O(n)
• 单调栈也能解

Resolution

我的解法

function trap(height: number[]): number {
    let res = 0
    const n = height.length
 
    const leftMax: number[] = Array.from({ length: n }, () => 0)
    leftMax[0] = height[0]
    for (let i = 1; i < height.length; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i])
    }
 
    const rightMax: number[] = Array.from({ length: n }, () => 0)
    rightMax[n - 1] = height[n - 1]
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i])
    }
 
    for (let i = 1; i < n - 1; i++) {
        res += Math.min(leftMax[i], rightMax[i]) - height[i]
    }
    return res
}

暴力解法（超时，O(n²)）

function trap(height: number[]): number {
    let res = 0
    for (let i = 1; i < height.length - 1; i++) {
        const leftMax = Math.max(...height.slice(0, i))
        const rightMax = Math.max(...height.slice(i + 1))
        const min = Math.min(leftMax, rightMax)
        if (leftMax > height[i] && rightMax > height[i]) {
            const curHeight = min - height[i]
            res += curHeight
        }
    }
    return res
}

每次 Math.max(...height.slice()) 重新扫描整个区间，O(n²) 超时。思路对，只是没预处理。

解题思路

每根柱子能接的水 = min(左侧最高, 右侧最高) - 当前高度。预处理两个数组：

• leftMax[i]：0 到 i 的最高值，从左到右扫一遍
• rightMax[i]：i 到 n-1 的最高值，从右到左扫一遍

最后遍历算水：min(leftMax[i], rightMax[i]) - height[i]

踩坑

• 暴力法 Math.max(...height.slice(0, i)) 每次重新扫描，O(n²) 超时
• 预处理数组空间换时间，查的时候 O(1)

复杂度

• 时间：O(n)，三次遍历
• 空间：O(n)，两个预处理数组