接雨水算法全解析：从错误到3种最优解法（含扩展与思路Trigger）

接雨水问题是数组类算法的经典“拦路虎”——既考察对“凹陷容量计算”的本质理解，又要求灵活运用单调栈、双指针等数据结构/技巧。本文将从最常见的错误入手，拆解3种正确解法（覆盖不同场景需求），延伸同类型问题的通用思路，帮你彻底吃透这类“边界约束容量”的问题。

一、题目背景：接雨水的核心需求与难点

题目描述

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

核心示例

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：14（经典测试用例，直观展示“凹陷储水”的核心）

本质与难点

储水本质：每个位置能接的水量 = 左右两侧最大高度的最小值 - 当前柱子高度（结果为正才有效）；
核心难点：如何高效找到每个位置的“左右最大高度”？如何避免冗余计算（时间/空间）？

与普通数组问题的区别

普通数组问题只需“单向遍历”，而接雨水需要“双向约束”（左右最大高度），因此需解决“如何同时兼顾两侧边界”的问题。

二、错误反思：用if代替while，漏掉的“连续凹陷”

最常见错误思路（单调栈版）

很多初学者会用单调栈思路，但因误用 if 代替 while，导致只处理了“单次凹陷”，漏掉了连续的多个凹陷（多个 mid_idx）：

# 错误代码（核心问题：if只弹一次栈）
def trap(height):if not height:return 0stack = []count = 0for i in range(len(height)):# 错误：if只能弹出1次，连续凹陷会漏算if stack and height[i] > height[stack[-1]]:mid = stack.pop()if not stack:breakleft = stack[-1]h = min(height[left], height[i]) - height[mid]w = i - left - 1count += h * wstack.append(i)return count

错误本质：漏掉“连续多个mid_idx”

当遇到比栈顶高的元素时，可能存在多个连续的凹陷需要计算（而非仅一个）。例如 height = [0,1,0,2,1,0,1,3]，遍历到 i=7（高度3）时，栈内有 [3,4,5,6]（对应高度2、1、0、1）：

3 > 1（栈顶6）→ 弹出6（mid1），计算水量；
3 > 0（栈顶5）→ 需继续弹出5（mid2），计算水量；
3 > 1（栈顶4）→ 需继续弹出4（mid3），计算水量；
3 > 2（栈顶3）→ 需继续弹出3（mid4），计算水量；

if 只能处理 mid1，剩下的 mid2-mid4 全部漏算，导致总水量少算。

反思总结

单调栈思路的核心是“连续弹出所有比当前元素矮的栈顶”，必须用 while 循环实现“持续弹出”，而非 if 的“单次弹出”——这是单调栈处理“连续凹陷”的关键。

三、3种正确解法：覆盖不同场景需求

解法一：单调栈（自底向上，批量处理凹陷）

核心逻辑

栈特性：单调递减栈（存储柱子索引，栈顶为当前最矮的凹陷底部）；
核心操作：遍历到比栈顶高的元素时，while 持续弹出栈顶（作为 mid_idx），新栈顶为 left_idx，当前元素为 right_idx，计算 (min(left_h, right_h) - mid_h) * (right_idx - left_idx - 1) 的水量；
本质：从“凹陷底部”向上计算，批量处理连续的凹陷。

正确代码（修正if→while）

def trap(height):if not height:return 0stack = []  # 存储索引，维持单调递减count = 0n = len(height)for i in range(n):# 关键：while持续弹出所有比当前元素矮的栈顶while stack and height[i] > height[stack[-1]]:mid_idx = stack.pop()if not stack:  # 无左边界，无法储水breakleft_idx = stack[-1]right_idx = i# 计算高度：左右边界最小值 - 凹陷底部高度h = min(height[left_idx], height[right_idx]) - height[mid_idx]# 计算宽度：左右边界间距 - 1w = right_idx - left_idx - 1count += h * wstack.append(i)return count

优缺点与适用场景

优点：一次遍历完成，代码紧凑，能批量处理连续凹陷；
缺点：需理解单调栈的弹出逻辑，思维门槛中等；
适用场景：熟悉单调栈操作，想在一次遍历中解决问题。

解法二：预处理左右最大高度（自左向右，直观易懂）

核心逻辑

分步计算：先通过两次线性遍历，分别得到每个位置的“左侧最大高度”和“右侧最大高度”，再第三次遍历计算每个位置的水量；
本质：直接套用“储水公式”，将“找左右最大高度”和“计算水量”分离，逻辑直观。

正确代码

def trap(height):if not height or len(height) < 2:return 0n = len(height)left_max = [0] * n  # left_max[i]：0~i的最大高度right_max = [0] * n  # right_max[i]：i~n-1的最大高度total = 0# 自左向右计算left_maxleft_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i-1], height[i])# 自右向左计算right_maxright_max[-1] = height[-1]for i in range(n-2, -1, -1):right_max[i] = max(right_max[i+1], height[i])# 逐位置计算水量for i in range(n):water = min(left_max[i], right_max[i]) - height[i]total += max(0, water)  # 负数取0（无法储水）return total

优缺点与适用场景

优点：逻辑最直观，无复杂数据结构，初学者入门首选；
缺点：需额外两个数组（空间O(n)），三次线性遍历；
适用场景：初学者、面试中追求“快速写对”，不纠结空间优化。

解法三：双指针贪心（O(1)空间，最优解）

核心逻辑

贪心思想：矮侧决定水位（若 left_max ≤ right_max，则左侧位置的水位上限由 left_max 决定，无需关注右侧更远的高度）；
双指针操作：left 从左向右，right 从右向左，动态维护 left_max 和 right_max，直接在“能确定水位”的一侧计算水量；
本质：对“预处理左右最大高度”的空间优化，用变量代替数组，空间从O(n)降至O(1)。

正确代码（优化后简洁版）

def trap(height):if len(height) < 2:return 0output = 0left, right = 0, len(height)-1left_max, right_max = height[left], height[right]while left < right:if left_max <= right_max:left += 1# 左侧水位由left_max决定，直接计算if height[left] < left_max:output += left_max - height[left]else:left_max = height[left]  # 更新左侧最大高度else:right -= 1# 右侧水位由right_max决定，直接计算if height[right] < right_max:output += right_max - height[right]else:right_max = height[right]  # 更新右侧最大高度return output

优缺点与适用场景

优点：时间O(n)、空间O(1)（最优复杂度），逻辑紧凑，面试加分；
缺点：需理解“矮侧决定水位”的贪心逻辑，思维门槛稍高；
适用场景：面试中追求空间优化，展示算法深度。

三种解法核心对比

解法	时间复杂度	空间复杂度	核心特点	适用人群
单调栈（自底向上）	O(n)	O(n)	批量处理连续凹陷，一次遍历	熟悉单调栈的开发者
预处理左右最大高度	O(n)	O(n)	逻辑最直观，分步计算	初学者、追求快速写对
双指针贪心（最优）	O(n)	O(1)	空间最优，贪心思想	面试进阶、追求极致优化

四、同类型扩展：“边界约束容量”问题通用思路

接雨水的核心是“找两侧边界的约束，计算中间凹陷容量”，这套思路可复用在多个经典问题中：

扩展1：盛最多水（LeetCode 11）

问题描述

给定n个非负整数，每个数代表坐标中的一个点 (i, ai)，画n条垂直线，找出其中两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

核心关联

与接雨水的异同：同样是“双指针+边界约束”，但盛最多水是“找最大宽×最小高”，接雨水是“逐位置算凹陷容量”；
解法：直接复用双指针思路，left 和 right 向中间收缩，优先移动矮侧（因为矮侧是容量瓶颈）。

代码片段

def maxArea(height):left, right = 0, len(height)-1max_water = 0while left < right:width = right - leftmin_h = min(height[left], height[right])max_water = max(max_water, width * min_h)# 移动矮侧，寻找更大的高度if height[left] < height[right]:left += 1else:right -= 1return max_water