接雨水

已关闭
dadingPython / C++入场费 3 金币0 次提交

题目描述

给定 n 个非负整数表示一个高度图,其中每根柱子的宽度为 1,计算下雨后能接住多少单位的水。

输入格式

第一行一个整数 n(1 ≤ n ≤ 10000),表示柱子的数量。 第二行 n 个非负整数,用空格分隔,表示每根柱子的高度。

输出格式

一个整数,表示下雨后能接住的总水量。

输入输出样例

样例 1

输入:

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

输出:

6

样例 2

输入:

5
4 2 0 3 2 5

输出:

11

说明/提示

双指针或单调栈都可以解决。考虑每个位置能存的水量取决于左右两边的最高柱子。