题解链接

Leetcode 42.接雨水-原题链接

题目内容

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

输入描述

输入共两行。

• 第一行为一个整数$n$，代表数组$height$的长度。

• 第二行为$n$个整数$height_0,height_1,...,height_{n-1}$，数字之间以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

12
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

输入

6
4 2 0 3 2 5

输出

9

提示

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