LeetCode 42. 接雨水

Categories:

Tags:

题目描述
思路分析
1. 解法一：双指针（推荐）
2. 解法二：动态规划（预处理左右最大值）
相似题目

题目描述

✅ 42. 接雨水

思路分析

解法一：双指针（推荐）

核心思路：

每个位置能接的雨水量取决于其左右两侧的最大高度中的较小值减去当前高度，即 water[i] = min(leftMax, rightMax) - height[i]。

双指针从两端向中间收缩，维护 leftMax 和 rightMax 分别记录左侧和右侧已遍历的最大高度。

关键推导：若 height[left] < height[right]，则 left 位置的右侧最大值一定 >= height[right] >= leftMax，因此 left 位置的储水量完全由 leftMax 决定，可以安全计算并移动 left 指针；右侧对称处理。

这样无需预先存储左右最大值数组，用 O(1) 空间完成计算。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，每个元素只被访问一次。

空间复杂度：O(1)，只使用了常数级别的额外空间。

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, res = 0;
        while (left < right) {
            // 左侧较矮，左侧储水量由 leftMax 决定
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    // 更新左侧最大高度
                    leftMax = height[left];
                } else {
                    // 当前位置可以储水
                    res += leftMax - height[left];
                }
                left++;
            } else {
                // 右侧较矮，右侧储水量由 rightMax 决定
                if (height[right] >= rightMax) {
                    // 更新右侧最大高度
                    rightMax = height[right];
                } else {
                    // 当前位置可以储水
                    res += rightMax - height[right];
                }
                right--;
            }
        }
        return res;
    }
}

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    res := 0

    for left < right {
        // 左侧较矮，左侧储水量由 leftMax 决定
        if height[left] < height[right] {
            if height[left] >= leftMax {
                // 更新左侧最大高度
                leftMax = height[left]
            } else {
                // 当前位置可以储水
                res += leftMax - height[left]
            }
            left++
        } else {
            // 右侧较矮，右侧储水量由 rightMax 决定
            if height[right] >= rightMax {
                // 更新右侧最大高度
                rightMax = height[right]
            } else {
                // 当前位置可以储水
                res += rightMax - height[right]
            }
            right--
        }
    }
    return res
}

解法二：动态规划（预处理左右最大值）

核心思路：

第一步预处理：从左到右扫描，leftMax[i] 记录 height[0..i] 的最大值。

第二步预处理：从右到左扫描，rightMax[i] 记录 height[i..n-1] 的最大值。

第三步：遍历每个位置，储水量为 min(leftMax[i], rightMax[i]) - height[i]，累加所有非负值即为答案。

思路直观，三次线性扫描即可完成，但需要额外 O(n) 空间存储两个辅助数组。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，进行了三次线性遍历。

空间复杂度：O(n)，其中 n 表示数组的长度，需要存储左右两个最大值数组。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // 预处理每个位置左侧（含自身）的最大高度
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 预处理每个位置右侧（含自身）的最大高度
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        // 累加每个位置的储水量
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}

func trap(height []int) int {
    n := len(height)
    // 预处理每个位置左侧（含自身）的最大高度
    leftMax := make([]int, n)
    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }
    // 预处理每个位置右侧（含自身）的最大高度
    rightMax := make([]int, n)
    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }
    // 累加每个位置的储水量
    res := 0
    for i := 0; i < n; i++ {
        res += min(leftMax[i], rightMax[i]) - height[i]
    }
    return res
}

相似题目

题目	难度	考察点
11. 盛最多水的容器	中等	双指针贪心
84. 柱状图中最大的矩形	困难	单调栈
238. 除自身以外数组的乘积	中等	前缀积 + 后缀积
407. 接雨水 II	困难	三维接雨水，优先队列
739. 每日温度	中等	单调递减栈
1793. 好子数组的最大分数	困难	双指针，与接雨水思路类似

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/96961914