#P4006. 接雨水

接雨水

题目内容

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

输入描述

输入共两行。

  • 第一行为两个个整数nn,代表数组heightheight的长度。

  • 第二行为nn个整数height0,height1,...,heightn1height_0,height_1,...,height_{n-1},数字之间以空格分隔。

输出描述

一个整数,表示答案。

样例1

输入

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

输出

说明

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

样例2

输入

6
4 2 0 3 2 5

输出

提示

  • n==height.lengthn == height.length
  • 1<=n<=21041 <= n <= 2 * 10^4
  • 0<=height[i]<=1050 <= height[i] <= 10^5