题意概括

给定 n 个非负整数，代表一个高度图，其中每个条形的宽度为 1。计算在下雨后，这个由条形图构成的容器总共能接住多少单位的雨水。

数据范围:

• $1 \le n \le 2 \times 10^4$
• $0 \le \text{height}[i] \le 10^5$

基础知识

“接雨水”是一个经典的算法问题。核心思想是，对于高度图中的任意一个位置 i，它能接到的雨水高度取决于其 左边的最高墙 和 右边的最高墙 中的 较矮者。具体来说，在位置 i 能接的雨水量为：

$$\text{water}[i] = \min(\text{max\_left\_height}[i], \text{max\_right\_height}[i]) - \text{height}[i] $$

其中 max_left_height[i] 是 height[0...i] 中的最大值，max_right_height[i] 是 height[i...n-1] 中的最大值。只有当这个差值为正时，才能接到水。

一个直接的方法是使用动态规划，创建两个辅助数组，分别预处理出每个位置的左侧最高墙和右侧最高墙。这需要 $O(N)$ 的时间复杂度和 $O(N)$ 的空间复杂度。

更优的解法是 双指针法，它可以在 $O(N)$ 的时间和 $O(1)$ 的额外空间内解决问题。

1. 初始化：设置两个指针，l 从数组左端开始，r 从右端开始。同时维护两个变量 lmx 和 rmx，分别记录 h[0...l] 和 h[r...n-1] 的最大高度。
2. 迭代：当 l < r 时循环：
   • 比较 h[l] 和 h[r]。
   • 如果 h[l] < h[r]，我们处理左指针 l。此时，我们能够确定 l 位置的雨水上限。因为 rmx 肯定大于等于 h[r]，而 h[r] 又大于 h[l]，所以 l 位置的瓶颈在于其左侧的最高墙 lmx。因此，该位置能接的雨水就是 lmx - h[l]。我们累加这个值，然后将 l 右移。
   • 如果 h[r] <= h[l]，逻辑对称。我们处理右指针 r。此时 r 位置的瓶颈在于其右侧的最高墙 rmx。该位置能接的雨水是 rmx - h[r]。累加后将 r 左移。
3. 终止：当 l 和 r 相遇时，遍历结束，我们便得到了雨水的总量。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    if (n < 3) {
        cout << 0 << endl;
        return;
    }

    int l = 0, r = n - 1;
    int lmx = 0, rmx = 0;
    ll ans = 0;

    while (l < r) {
        if (h[l] < h[r]) {
            // 左边是短板，处理左指针
            if (h[l] >= lmx) {
                // 当前墙更高，不能存水，更新左侧最高墙
                lmx = h[l];
            } else {
                // 当前墙更矮，可以存水
                ans += lmx - h[l];
            }
            l++;
        } else {
            // 右边是短板或一样高，处理右指针
            if (h[r] >= rmx) {
                // 更新右侧最高墙
                rmx = h[r];
            } else {
                ans += rmx - h[r];
            }
            r--;
        }
    }
    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
12
0 1 0 2 1 0 1 3 2 1 2 1
输出:
6

样例 2:
输入:
6
4 2 0 3 2 5
输出:
9
*/