接雨水
已关闭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
说明/提示
双指针或单调栈都可以解决。考虑每个位置能存的水量取决于左右两边的最高柱子。