10. Trapping Rain Water

Difficulty: hard · Array, Two Pointers, Stack

Problem

Given `n` non-negative integers describing an elevation map where every bar has width `1`, compute how much water it can trap after raining. Water above a bar rises to the lower of the tallest bar on its left and the tallest bar on its right.

Input

The first line holds `n`. The second holds `n` bar heights.

Output

Print the total units of trapped water.

Example 1

Input:
12
0 1 0 2 1 0 1 3 2 1 2 1
Output:
6

Explanation: Water settles in the dips between taller bars: 6 units in total.

Example 2

Input:
6
4 2 0 3 2 5
Output:
9

Explanation: Water settles in the dips between taller bars: 9 units in total.

Example 3

Input:
1
5
Output:
0

Explanation: No bar has a taller bar on both sides of it, so no water is held.

Example 4

Input:
3
1 2 3
Output:
0

Explanation: No bar has a taller bar on both sides of it, so no water is held.

Example 5

Input:
3
3 0 3
Output:
3

Explanation: Water settles in the dips between taller bars: 3 units in total.

Example 6

Input:
5
5 4 3 2 1
Output:
0

Explanation: No bar has a taller bar on both sides of it, so no water is held.

Example 7

Input:
5
2 0 2 0 2
Output:
4

Explanation: Water settles in the dips between taller bars: 4 units in total.

Example 8

Input:
7
0 3 0 0 0 3 0
Output:
9

Explanation: Water settles in the dips between taller bars: 9 units in total.

Example 9

Input:
8
1 5 5 2 0 1 5 5
Output:
12

Explanation: Water settles in the dips between taller bars: 12 units in total.

Example 10

Input:
6
4 1 3 6 1 6
Output:
9

Explanation: Water settles in the dips between taller bars: 9 units in total.

Constraints

- 1 <= n <= 2 * 10^4 - 0 <= height[i] <= 10^5

Solutions are judged against 10 sample and 5 hidden tests. Sign in to solve it · All problems