1966: 阳台接雨
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:160
解决:40
题目描述
家里阳台有一排水平摆放的花架,均匀固定了 n 块垂直挡板(挡板底部与花架贴合,无空隙)。设第 i 块挡板的高度为 aᵢ(单位:米,i=1,2,…,n),相邻挡板无空隙。
暴雨后雨水均匀落在花架上且无渗漏,积水高度遵循 “不超过两侧挡板的最低值、不溢出当前挡板” 的规则(即某位置积水高度 = 该位置左右两侧最高挡板中的较低值 - 当前挡板高度,若结果为负则无积水)。每 1 立方米雨水可浇灌 1 盆花,这排花架最多能储存多少立方米雨水?
输入
第一行一个整数n,表示n块挡板。
接下来是挡板高度数组
输出
一个整数,表示这排花架最多能储存的立方米雨水。
样例输入 复制
12
0 1 0 2 1 0 1 3 2 1 2 1
样例输出 复制
6
提示
1 <= n <= 2 * 10^4
0 <= a[i] <= 10^5