LeetCode 42. 接雨水

2026-09-02 HGNULB 约 4 分钟

文章信息 23 个分类 6 个标签

分类

LeetCode CodeTop 困难已解决需复习 200-500 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多小米虾皮小红书 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 42. 接雨水

题意分析

输入一个非负整数数组 height，height[i] 表示第 i 根柱子的高度，每根柱子宽度都是 1。下雨之后柱子形成的凹陷会积水，要求返回总共能接多少单位的水。

题目只要一个总量，不要求还原水面形状或者说明水从哪里溢出，这提示答案可以被拆成互不干扰的小块累加。最自然的拆法是按列而不是按凹陷块：整个水面被 n 条宽度为 1 的竖直细条铺满，第 i 条的体积就是「该列水面高度减去柱子高度」。

一旦按列拆开，就能发现一个决定性的物理模型：每个位置的储水量 = min(左侧最高, 右侧最高) − 自身高度，算出来不是正数就说明这一列存不住水。水面高度只由两侧极值中较小的那个决定，和柱子的具体分布无关——较小的一侧才是水的溢出口，水面不可能高过它；而只要两侧都比当前柱子高，中间的低洼就一定会被填平。这条公式是本题所有高效做法的共同出发点。

需要单独想清楚的边界：数组长度为 0、1、2 时答案必为 0；两端的柱子永远接不到水，因为其中一侧没有任何柱子挡着；单调不减或单调不增的数组接不到水；所有柱子等高时答案也是 0。这些情形都应当由公式自然给出 0，而不是靠额外的特判打补丁。

解法：双指针

核心思路

每个位置的积水量是 min(左侧最高柱, 右侧最高柱) - height[i]。双指针从两端向中间移动：当前较矮的一端已有另一端兜底，其积水量只由本侧历史最高值决定，可以立即结算。

解题步骤

初始化左右指针、本侧最高值和答案。

比较 height[left] 与 height[right]，结算较矮的一侧。

若当前柱低于本侧最高值，累加高度差；否则更新本侧最高值。

移动已结算的指针，直到两指针相遇。

代码实现

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
}

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

    for left < right {
        if height[left] <= height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}

复杂度分析

时间复杂度：$O(n)$，每个位置最多处理一次。

空间复杂度：$O(1)$。

关键点总结

单列水位由左右最高柱中较矮的一根决定。

每轮只结算边界较矮的一侧，另一端保证水不会从该侧溢出。

历史最高值既是挡板高度，也是当前列积水量的计算依据。

易错点总结

水位应取两侧最高值的较小值，而不是较大值。

先结算较高的一侧会缺少另一侧足够高的挡板保证。

柱高不低于本侧最高值时应更新最高值，不能累加负数。

相似题目

题目	难度	考察点
11. 盛最多水的容器	中等	同样从两端向内收缩，但结算的是单个矩形面积，移动依据是「较矮的边不可能更优」
84. 柱状图中最大的矩形	困难	求的是最大单块矩形而非总量，无法逐列独立累加，必须用单调栈定位左右边界
238. 除自身以外数组的乘积	中等	前后缀预处理的同一套模板，把「取极值」换成「求乘积」，并要求不用除法
407. 接雨水 II	困难	升到二维网格后「左右两侧」变成四周边界，只能从最外圈用优先队列向内淹没
面试题 17.21. 直方图的水量	困难	与本题同题，可用来分别默写双指针和前后缀两版并对照答案