问题2400--小G的日常之接雨水

2400: 小G的日常之接雨水

时间限制: 1 Sec  内存限制: 128 MB
提交: 243  解决: 79
[状态] [讨论版] [提交] [命题人:]
题目描述

下雨了,小G想到了一个问题,给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
你能帮帮小G吗?

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

输入

第一行,输入一个数n(1 <= n <= 1,000,000)
第二行,输入n个数 (这n个数小于1e9)

输出

可以接多少雨水。

样例输入 Copy
12
0 1 0 2 1 0 1 3 2 1 2 1
样例输出 Copy
6
来源/分类