AcWing 1574. 接雨水

题目

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

例如，当给定数字序列为 0,1,0,2,1,0,1,3,2,1,2,1 时，柱子高度图如下所示，最多可以接 个单位的雨水。

输入格式

第一行包含整数 。

第二行包含 个非负整数。

输出格式

输出一个整数，表示最大接水量。

数据范围

,
序列中元素均不大于 。

输入样例：

12
0 1 0 2 1 0 1 3 2 1 2 1

输出样例：

6

题解

#include <iostream>

using namespace std;

const int N = 100010;

int h[N], q[N];
int n;

int main()
{
    scanf("%d", &n);

    int res = 0, tt = -1;

    // 单调递减栈，找到左边第一个高度大于自己的柱子，在出栈时加上雨水
    for (int i = 0; i < n; ++ i) 
    {
        scanf("%d", &h[i]);

        int last = 0;
        while (tt >= 0 && h[q[tt]] <= h[i])
        {
            // 高度等于当前出栈柱子减去上一个柱子高度
            res += (h[q[tt]] - last) * (i - q[tt] - 1);
            last = h[q[tt]];
            -- tt;
        }
        // 出最后一根小于自己的柱子时，高度等于当前柱子高度减去出栈柱子高度
        if (tt >= 0) res += (h[i] - last) * (i - q[tt] - 1);
        q[++ tt] = i;
    }

    cout << res << endl;
}