1386: 【中级组】接雨水

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：68 Solved：26

Description

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


      


 示例1： 

输入：n=12, height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
 输出：6  解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示            的高度图，在这种情况下，可以接 6 个单位的            雨水（蓝色部分表示雨水）。 示例2： 输入：n=6, height[] = {4,2,0,3,2,5}; 输出：9 

Input

          输入共二行,第一行为 n 。第二行为 height 数组。数据之间用空格分隔。

Output

        计算按此排列的柱子，输出下雨之后能接多少雨水。 

Sample Input Copy 

8
3 2 1 1 0 0 2 3

Sample Output Copy 

12

HINT

提示：

  • 1 <= n <=100
  • 0 <= height[i] <= 100