一、题目解析
1.1 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度，计算按此排列的柱子下雨之后能接多少雨水。
输入是一个数组 heights，输出是积水总量。
1.2 示例
plain text
输入： [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]输出： 6问题本质：对于每一段凹槽（两个较高的柱子夹着较低的柱子），接水量取决于左右两边较矮的那根柱子与槽底的差值，再乘以宽度。
二、思路分析
2.1 接水的条件
能接水的场景可以描述为：从左到右依次看柱子，当遇到一根比前面更高的柱子时，前面那根较矮的柱子就成为一个"槽底"，它和左右两根更高的柱子围成了一个能积水的凹槽。
更精确地说，对于任意三根柱子——左边的 left、中间的 bottom、右边的 right——只要 heights[left] > heights[bottom] 且 heights[right] > heights[bottom]，bottom 上方就能积水。==水量 = (min(左高, 右高) − 槽底高) × 宽度。==
2.2 单调栈：逐层计算
维护一个栈底到栈顶严格递减的单调栈，存的是柱子的索引（不是高度），栈内索引对应的柱子高度是递减的。
遍历每根柱子 i：
- 如果当前柱子高度 ≤ 栈顶柱子高度，直接入栈——它可能成为未来的槽底。
- 如果当前柱子高度 > 栈顶柱子高度，说明找到了一个"右墙"，可以开始结算积水：
- 弹出栈顶，记作
bottom（槽底） - 如果栈空了，说明左边没有墙，这个槽底左边不会积水，跳过
- 新的栈顶
left是左墙，i是右墙 - 宽度 =
right − left − 1 - 高度 =
min(heights[right], heights[left]) − heights[bottom] - 水量 = 宽度 × 高度，累加到答案
- 结算完后，继续检查新的栈顶——因为当前右墙可能比新的栈顶也高，能结算更高一层的积水
- 弹出栈顶，记作
一次弹栈只结算一个"水平层"的水量，而不是一整列。同一段位置可能被多次结算（不同高度层），但每层宽度和高度不同，总和等于实际水量。
三、代码实现
java
class Solution { public int trap(int[] heights) { // 单调递减栈，存的是柱子的索引 Deque<Integer> stack = new ArrayDeque<>(); int ans = 0; for (int i = 0; i < heights.length; i++) { // 当前柱子比栈顶高 → 找到右墙，开始结算积水 while (!stack.isEmpty() && (heights[stack.peekLast()] < heights[i])) { // 槽底的索引 int bottomIndex = stack.pollLast(); // 栈空了说明左边没有墙，无法积水 if (stack.isEmpty()) { break; } // 右墙 = 当前柱子，左墙 = 新的栈顶 int right = i; int left = stack.peekLast(); int width = right - left - 1; int height = Math.min(heights[right], heights[left]) - heights[bottomIndex]; ans += width * height; } stack.addLast(i); } return ans; }}例子里最关键的结算发生在 i=7（高度 3 的柱子）：
- 第一轮弹出
bottom=6（高 1），left=4（高 1），right=7（高 3），min(3,1)-1=0，宽度 2，水量 0——这一层没有实际积水，因为左右等高 - 第二轮弹出
bottom=4（高 1），left=3（高 2），right=7（高 3），min(3,2)-1=1，宽度 3，水量 3 - 第三轮弹出
bottom=3（高 2），栈空，break
最终在 i=7 这一轮结算了 3 单位水。
四、图解过程
以 [0,1,0,2,1,0,1,3,2,1,2,1] 为例：
| 步骤 | i | 现象 | 结算 |
|---|---|---|---|
| i=1 | 1 | 1 > 0，弹出 0 后栈空 | 无左墙，跳过 |
| i=3 | 3 | 2 > 0(栈顶=索引2)，弹出 bottom=2 | left=1, right=3, 宽1高1, +1 |
| 2 > 1(栈顶=索引1)，弹出 bottom=1 后栈空 | 跳过 | ||
| i=6 | 6 | 1 > 0(栈顶=索引5)，弹出 bottom=5 | left=4, right=6, 宽1高1, +1 |
| i=7 | 7 | 3 > 1(栈顶=索引6)，弹出 bottom=6 | left=4, right=7, 宽2高0, +0 |
| 3 > 1(栈顶=索引4)，弹出 bottom=4 | left=3, right=7, 宽3高1, +3 | ||
| 3 > 2(栈顶=索引3)，弹出 bottom=3 后栈空 | 跳过 | ||
| i=10 | 10 | 2 > 1(栈顶=索引9)，弹出 bottom=9 | left=8, right=10, 宽1高1, +1 |
累计：1 + 1 + 3 + 1 = 6。每个弹出结算一层水，宽度 × 高度就是那一层的面积。
五、复杂度分析
时间复杂度：O(n)。每个索引最多入栈一次、出栈一次，while 里的结算循环不会让同一个元素被反复处理，均摊 O(1)。
空间复杂度：O(n)。最坏情况是柱子高度严格递减，栈的大小等于 n。
本文由 AgentPlanFlow 生成