LC42. 接雨水

题目描述

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

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

题目解析

题目在说什么

想象一下，你有一排高低不同的柱子（高度用数组表示），比如 [0,1,0,2,1,0,1,3,2,1,2,1]。每个柱子宽度是1，它们并排站在一起。下雨之后，雨水会积在柱子之间的低洼处，就像你用手在沙子里按出几个坑，水会留在坑里一样。题目要你计算：这些柱子能接住多少单位的雨水？每个单位相当于一个1x1的小方块。

比如上面那个例子，答案是6，意思是能接6个单位的雨水。你可以把柱子想象成“墙”，雨水就是“被困在墙之间的水”。

思路是怎么来的

从生活场景出发

假设你有一排积木块，高度不同。你想知道下雨后哪些地方会积水。积水的地方一定是“两边高、中间低”的凹槽。比如，两个高柱子中间夹着一个矮柱子，水就会积在矮柱子的上面。

关键问题：怎么找到这些凹槽？一个凹槽由三个柱子组成：左边柱子、底部柱子、右边柱子。左边和右边要高，底部要低。比如，柱子高度 [2,1,3] 中，左边2、底部1、右边3，中间就能积水。

为什么用栈？

我们从头到尾看柱子，边走边判断。如果新来的柱子比前面一个高，就可能和前面的柱子形成凹槽。但前面可能有多个柱子，我们需要一个结构来记住“还没处理完的柱子”。栈（Stack）就像一个“待处理清单”，后进先出，很适合处理这种“新元素和旧元素比较”的问题。

具体来说：

• 栈里存的是柱子的下标（位置），不是高度。
• 我们维护一个“单调递减”的栈：从栈底到栈顶，高度越来越小。这样，新来的柱子如果比栈顶高，就说明栈顶柱子可能是凹槽的底部，而栈里它前面的柱子是左边，新柱子是右边。

三种情况

遍历每个柱子时，和栈顶比较： 1. 新柱子 < 栈顶：无法形成凹槽（因为右边不够高），直接入栈。 2. 新柱子 == 栈顶：同样无法形成凹槽（高度相等，没有低洼），直接入栈。 3. 新柱子 > 栈顶：可能形成凹槽！此时栈顶是底部，栈里下一个是左边，新柱子是右边。计算这个凹槽的面积，然后弹出栈顶（底部），继续检查栈里剩下的元素能否和新柱子再形成凹槽。

注意：即使新柱子大于栈顶，也可能形成面积为0的凹槽（比如左边和底部一样高），但计算时面积会是0，不影响结果。

代码逐步拆解

我们对照参考代码（Java），一步步看它在做什么。

第一步：特殊情况处理

if (height.length <= 2) return 0;

• 如果柱子少于3根，不可能有凹槽（至少需要左、底、右三根），直接返回0。

第二步：初始化

Stack<Integer> stack = new Stack<>();
int result = 0;

• 创建一个栈，用来存柱子下标。
• result 记录总雨水量。

第三步：遍历每个柱子

for (int i = 0; i < height.length; i++) {

• 从左边第一个柱子开始，逐个处理。

第四步：栈为空时

if(stack.isEmpty()){
    stack.push(i);
}

• 如果栈是空的，直接把当前柱子下标放进去。因为凹槽需要至少两个柱子才能形成，第一个柱子先入栈等待。

第五步：新柱子小于栈顶

else if (height[i] < height[stack.peek()]) {    
    stack.push(i);
}

• 新柱子比栈顶矮，无法形成凹槽（右边不够高），直接入栈。栈保持递减顺序。

第六步：新柱子等于栈顶

if (height[i] == height[stack.peek()]) {
    stack.push(i);
}

• 高度相等，也无法形成凹槽（没有低洼），直接入栈。注意：这里代码用了 if 而不是 else if，但逻辑上没问题，因为前一个条件已经排除了小于的情况。

第七步：新柱子大于栈顶（核心逻辑）

else {
    while (!stack.empty() && height[i] > height[stack.peek()]) {

• 新柱子比栈顶高，可能形成凹槽。用 while 循环，因为可能连续弹出多个栈顶，每个都和新柱子形成凹槽。

7.1 获取底部

int bottom = stack.peek();
stack.pop();

• bottom 是当前栈顶的下标，也就是凹槽的底部柱子。弹出它，因为我们要用它计算面积，然后看栈里剩下的元素。

7.2 检查左边是否存在

if (!stack.empty()) {

• 如果栈不为空，说明底部左边还有柱子，可以形成凹槽。如果栈为空，说明左边没有柱子，无法形成凹槽（比如只有一根柱子）。

7.3 计算高度

int h = Math.min(height[stack.peek()], height[i]) - height[bottom];

• 凹槽的高度 = min(左边高度, 右边高度) - 底部高度。
• 左边高度是栈里下一个元素（即弹出底部后的新栈顶），右边高度是当前新柱子。