接雨水 图解题解

接雨水这道题在问什么

给一排宽度为 1、高度不等的柱子，下雨后凹槽里会存水，求总共能接多少格水。关键的物理直觉是按「竖列」看：某一列上方能存的水，取决于它左边的最高柱和右边的最高柱——水面高度是两者中较矮的那个，再减去这一列自身的高度，就是这一列的储水量；如果自身比两边最高墙还高，这一列存不了水。

从每列扫两遍到双指针的推导

把上面的直觉直接翻译成代码，就是对每一列分别向左、向右扫一遍找最高墙，n 列各扫 O(n)，总共 O(n²)，柱子一多就太慢。第一步优化是用两个数组预处理出「每个位置左侧最高」和「右侧最高」，查询变 O(1)，时间降到 O(n)，但要 O(n) 的额外空间。

再进一步观察：结算一列时，其实不需要同时精确知道左右两边的最高墙，只需要知道「较矮的那一边有多高」。这就是双指针版本省掉数组的突破口。

为什么只看较矮的一端就能定水量

让左指针 l 从最左、右指针 r 从最右往中间走，一路维护 leftMax（l 左侧走过的最高柱）和 rightMax（r 右侧走过的最高柱）。每轮比较两端柱高：假设左端更矮，那么右边一定存在一根不低于当前右端的柱子挡着，水面下限已经被左侧锁死——这一格的水量就是 leftMax 减去自身高度，跟右边究竟多高无关。右端更矮时对称处理。

这就是「木桶短板」的贪心论证：较矮的一端是当前的瓶颈，它的储水量当场可以拍板，所以放心结算并把该指针往中间挪一格。每格恰好被结算一次，两个指针合计走完整个数组，正确性和 O(n) 的效率同时成立。

循环里最容易写错的三个地方

一是减错基准：某格的水量是「一侧最高墙减自身」，不是拿相邻柱子或自身高度做差；二是指针移动方向：每轮必须移较矮的那一端，若总是移左指针，右侧瓶颈没被结算就被跳过，答案偏小；三是判断顺序：当前柱不低于本侧 max 时它自己就是新墙，要先更新 max 且这一格不接水，只有严格矮于 max 才累加 max 减自身。

复杂度与另一条单调栈思路

双指针版时间 O(n)：l 和 r 相向而行，每格只处理一次；空间 O(1)：全程只有 l、r、leftMax、rightMax 和累加器五个变量。

这道题还有一条按「横条」结算的思路——单调递减栈：遇到比栈顶高的柱子就出栈结算一层横向的水。同样是 O(n) 时间，但要 O(n) 的栈空间。面试里双指针是空间最优解，单调栈则更适合作为理解「按层算水」的补充视角，两种都值得会讲。

Python

def trap(height):
    l, r = 0, len(height) - 1
    lmax = rmax = total = 0
    while l < r:
        if height[l] < height[r]:
            if height[l] >= lmax: lmax = height[l]
            else: total += lmax - height[l]
            l += 1
        else:
            if height[r] >= rmax: rmax = height[r]
            else: total += rmax - height[r]
            r -= 1
    return total

C++

int trap(vector<int>& h){
    int l = 0, r = h.size() - 1;
    int lmax = 0, rmax = 0, total = 0;
    while(l < r){
        if(h[l] < h[r]){
            h[l] >= lmax ? lmax = h[l] : total += lmax - h[l];
            l++;
        } else {
            h[r] >= rmax ? rmax = h[r] : total += rmax - h[r];
            r--;
        }
    }
    return total;
}

Java

public int trap(int[] height) {
    int l = 0, r = height.length - 1;
    int lmax = 0, rmax = 0, total = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= lmax) lmax = height[l];
            else total += lmax - height[l];
            l++;
        } else {
            if (height[r] >= rmax) rmax = height[r];
            else total += rmax - height[r];
            r--;
        }
    }
    return total;
}