#A. 接雨水问题

problem_type.default

1000ms

256MiB

대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

描述

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：数组长度 0≤n≤2×105，数组中每个值满足 0<val≤109 ，保证返回结果满足 0≤val≤109

要求：时间复杂度 O(n)

输入：

[3,1,2,5,2,4]

返回值：

说明：

数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。

输入：

[4,5,1,3,2]

返回值：