1574. 接雨水
题目描述
给定 $n$ 个非负整数表示每个宽度为 $1$ 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
例如,当给定数字序列为 0,1,0,2,1,0,1,3,2,1,2,1
时,柱子高度图如下所示,最多可以接 $6$ 个单位的雨水。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个非负整数。
输出格式
输出一个整数,表示最大接水量。
数据范围
$1 \le n \le 10^5$,
序列中元素均不大于 $1000$。
输入样例:
12
0 1 0 2 1 0 1 3 2 1 2 1
输出样例:
6
算法
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int h[N];
int q[N], tt = -1;
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &h[i]);
int res = 0;
for(int i = 0; i < n; i ++)
{
while(tt >= 0 && h[q[tt]] <= h[i])
{
int top = q[tt--];
if(tt >= 0)
res += (i - q[tt] - 1) * (min(h[q[tt]], h[i]) - h[top]);
}
q[++tt] = i;
}
printf("%d", res);
return 0;
}