Leetcode 42.接雨水-原题链接

题目内容

有一排宽度均为 $1$ 的柱子，它们的高度由一个长度为 $n$ 的非负整数数组 $height$ 表示。降雨停止后，雨水会积存在柱子之间的低洼区域。请计算这些柱子按给定顺序排列时，总共能够存留多少个单位的雨水。

约束条件：

• 数组 $height$ 的长度 $n$ 满足 $1 \le n \le 2 \times 10^4$。
• 每个高度 $height[i]$ 都是非负整数，且不超过 $10^5$。

输入描述

输入一共两行。 第一行包含一个整数 $n$，表示高度数组 $height$ 的长度。 第二行按顺序包含 $height_0, height_1, \ldots, height_{n-1}$，相邻整数之间用一个空格分隔。

输出描述

输出一行一个整数，表示能够存留的雨水总量。

样例1

输入

6
4 2 0 3 2 5

输出

9

说明

高度数组为 4、2、0、3、2、5。

位置 0 是左边界，无法存水，存水量为 0。

位置 1 的左侧最高为 4，右侧最高为 5，水位上限为 $\min(4,5)=4$，当前高度为 2，因此存水量为 $4-2=2$。

位置 2 的左侧最高为 4，右侧最高为 5，水位上限为 $\min(4,5)=4$，当前高度为 0，存水量为 $4-0=4$。

位置 3 的左侧最高为 4，右侧最高为 5，水位上限为 $\min(4,5)=4$，当前高度为 3，存水量为 $4-3=1$。

位置 4 的左侧最高为 4，右侧最高为 5，水位上限为 $\min(4,5)=4$，当前高度为 2，存水量为 $4-2=2$。

位置 5 是右边界，无法存水，存水量为 0。

总存水量为 $0+2+4+1+2+0=9$。

样例2

输入

1
7

输出

0

说明

数组长度为 1，只有一个高度为 7 的柱子。

只有一根柱子无法围成低洼区域，因此不能存留雨水，总存水量为 0。

样例3

输入

5
5 4 3 2 1

输出

0

说明

高度数组为 5、4、3、2、1。

柱子高度从左到右严格递减，每个位置右侧的柱子都不高于当前柱子，无法形成阻挡水流的右侧边界，因此不会积存雨水，总存水量为 0。