LeetCode 第 42 题《接雨水》是一道非常经典的题目，涵盖了从模拟、动态规划、双指针到单调栈等多种核心算法思想。

---

part 1. 题目描述

题目名称：雨水收集 (Trapping Rain Water)

【题目描述】

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

想象一下，这些柱子立在地面上，当雨水落下时，凹陷的地方会积水。你需要计算出所有凹陷处积水的总体积（我们假设水的宽度与柱子一致，忽略蒸发和侧漏，仅考虑二维截面）。

【输入格式】

输入共两行： 第一行包含一个整数 $n$，表示柱子的数量。 第二行包含 $n$ 个非负整数 $h_1, h_2, \dots, h_n$，之间用空格分隔，分别表示每个柱子的高度。

【输出格式】

输出共一行，包含一个整数，表示能接到的雨水总量。

【样例 1】

输入：

12
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 个单位的雨水（蓝色部分）。

【样例 2】

输入：

6
4 2 0 3 2 5

输出：

9

【数据范围与提示】

对于 $100\%$ 的数据，满足：

• $1 \le n \le 2 \times 10^4$
• $0 \le h_i \le 10^5$

---

Part 2. 教练指导：预备知识点

在解决这道题之前，你需要掌握以下知识点：

1. 数组与模拟：基本的数组遍历和逻辑判断。
2. 前缀/后缀最值（动态规划思想）：预处理数组区间的最值信息。
3. 双指针 (Two Pointers)：利用单调性从两端向中间逼近，优化空间复杂度。
4. 单调栈 (Monotonic Stack)：处理“找左右第一个比自己大/小的元素”这类问题的利器。

---

Part 3. 读题关键词：如何快速切题

在读题时，请圈出以下关键词，它们决定了你的建模方式：

1. “宽度为 1”：这意味着我们可以在水平方向上离散化，单独考虑每一列（下标 $i$）能存多少水。
2. “凹陷”：水能存住的本质是因为“两边高，中间低”。
3. “木桶效应” (Shortest Plank)：对于某一个位置，它上面能存多少水，取决于它左边最高的柱子和它右边最高的柱子中较矮的那一个。

---

Part 4. 启发式教学：草稿纸上的推理演变

好，同学们，拿出草稿纸，我们来画图分析。不要急着写代码，先想清楚逻辑。

思路一：按“列”求（纵向切分）—— 朴素到 DP

引导提问 1： 看着图，请问下标为 $i$ 的这根柱子顶上能存多少水？

• 学生思考： 如果它左边有个很高的墙，右边也有个很高的墙，水就能存住。
• 教练点拨： 具体是多少？假设左边最高的墙高度是 max_left，右边最高的墙是 max_right。
  • 如果 min(max_left, max_right) > height[i]，那么存水量 = min(max_left, max_right) - height[i]。
  • 否则，存不下水（水会流走），也就是 0。

引导提问 2： 如果我们对每个 $i$ 都去暴力向左向右找最大值，复杂度是多少？

• 推导： 对每个点遍历整个数组，$O(n^2)$。数据范围 $n=2 \times 10^4$，这在 NOI 中可能会超时（或勉强过），但不够好。

优化思路（DP）：

• 我们能不能预先把“每个位置左边的最大值”和“右边的最大值”算出来存好？
• 草稿纸操作：
  • 定义 left_max[i]：表示 $0 \dots i$ 范围内的最大高度。公式：left_max[i] = max(left_max[i-1], height[i])。
  • 定义 right_max[i]：表示 $i \dots n-1$ 范围内的最大高度。公式：right_max[i] = max(right_max[i+1], height[i])。
• 复杂度分析：
  • 时间：预处理 $O(n)$ + 计算 $O(n) = O(n)$。
  • 空间：需要两个辅助数组，$O(n)$。

---

思路二：空间优化 —— 双指针 (Two Pointers)

引导提问 3： 在 DP 解法中，我们真的需要把所有 right_max 都存下来吗？

• 图解分析： 想象两个指针 left 和 right 分别在数组两头。
  • 维护 left_max 和 right_max 变量。
  • 如果 left_max < right_max：说明左边这面墙是“短板”。对于 left 指针指向的位置，右边一定有比 left_max 更高的墙（哪怕就是当前的 right_max），所以该位置的水量完全由 left_max 决定。
  • 反之亦然。

结论：

• 我们只需要两个指针向中间靠拢，谁那边的“墙”矮，就计算谁、并移动谁。
• 复杂度分析： 时间 $O(n)$，空间 $O(1)$。这是 NOI 中最优的解法之一。

---

思路三：按“层”求（横向切分）—— 单调栈

引导提问 4（进阶）： 刚才我们是一列一列算的。现在换个思路，如果有凹槽，我们能不能像填坑一样，直接算出这个坑水的体积？

• 场景模拟： 遍历柱子，如果当前的柱子比栈顶的柱子矮，说明可能形成坑底，入栈；如果当前的柱子比栈顶高，说明右边界出现了！

• 操作步骤：

  1. 栈中存储下标（为了算宽度）。
  2. 遇到高柱子 current 时，弹出栈顶 top（这是坑底）。
  3. 此时，新的栈顶 stack.top() 是左边界，current 是右边界。
  4. 高度 = min(height[left], height[right]) - height[bottom]。
  5. 宽度 = right - left - 1。
  6. 体积 = 高度 $\times$ 宽度。

• 关键词总结： 找左边和右边第一个比自己大的元素 $\rightarrow$ 单调递减栈。

---

Part 5. 复杂度总结与建议

方法	时间复杂度	空间复杂度	评价
暴力模拟	$O(N^2)$	$O(1)$	易超时，不推荐
动态规划	$O(N)$	$O(N)$	思路清晰，适合初学者
双指针		$O(1)$	最优解，省空间，推荐掌握
单调栈		$O(N)$	适合理解“横向”积水逻辑，处理更复杂变种题时有用

优化建议： 在考场上，如果对空间没有极致苛刻的要求（比如内存限制 2MB），写 DP 数组是最稳妥、最不易出错的。如果追求极致或数据规模极大，使用双指针。

---

Part 6. NOI 风格参考代码 (C++14)

这里提供 双指针解法 的标准代码，因为它是空间最优解，且代码简洁，符合竞赛中追求效率的习惯。

/**
 * NOI Style Solution
 * Problem: Trapping Rain Water
 * Method: Two Pointers (Space Optimized)
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio> // 使用 scanf/printf 是 NOI 选手的传统艺能，虽然 cin 关同步也很快

using namespace std;

// 全局变量定义，防止栈溢出（本题数据不大，但在大数据题中是好习惯）
const int MAXN = 20005; // 根据题目 n <= 2*10^4
int h[MAXN];
int n;

void solve() {
    if (n == 0) {
        printf("0\n");
        return;
    }

    int left = 0;
    int right = n - 1;
    
    int left_max = 0;
    int right_max = 0;
    
    long long ans = 0; // 即使题目保证整数范围，累加和习惯性开 long long 防止溢出

    while (left <= right) {
        // 判断哪边的挡板是瓶颈
        if (left_max <= right_max) {
            // 左边是短板，处理左指针
            // 更新左边遇到的最高墙
            left_max = max(left_max, h[left]);
            // 当前柱子能存的水 = 左边最高墙 - 当前高度
            // 注意：如果 current == left_max，结果是 0，符合逻辑
            ans += (left_max - h[left]);
            left++;
        } else {
            // 右边是短板，处理右指针
            right_max = max(right_max, h[right]);
            ans += (right_max - h[right]);
            right--;
        }
    }

    printf("%lld\n", ans);
}

int main() {
    // 提升 cin/cout 效率，虽然本例使用 scanf，但保留此习惯
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);

    // 读入 n
    if (scanf("%d", &n) != EOF) {
        // 读入数组
        for (int i = 0; i < n; i++) {
            scanf("%d", &h[i]);
        }
        solve();
    }

    return 0;
}

代码细节批注（教学用）：

1. long long ans：虽然这道题 $2 \times 10^4 \times 10^5$ 理论上可能爆 int（虽然实际用例可能不会），但在竞赛中，累加结果首选 long long 以防万一。
2. left <= right：循环条件的细节。实际上当 left == right 时，也就是最后一个柱子，虽然它的存水量肯定是 0（因为它是最高的之一），但为了逻辑完整性通常会让指针交错结束。
3. 短板效应：if (left_max <= right_max) 是双指针的核心。只要确定了左边比右边低，那么对于 left 这个位置，其实际蓄水高度上限就被牢牢锁定在了 left_max，不用管右边那个很远的 right_max 到底有多高，因为它肯定比 left_max 高。