170. Trapping Rain Water
Challenge1000 ms256 MBSolved by 0%
Given n bars of width 1 with the given heights, work out how much rainwater
is trapped between them after it rains, and print the total.
Water sits above a bar up to the level of the lower of the two tallest walls on either side of it. Water at the open ends runs off.
For [0,1,0,2,1,0,1,3,2,1,2,1] the answer is 6.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ height ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, the total units of water trapped.
Input12
0 1 0 2 1 0 1 3 2 1 2 1
Output6
Noteis the worked example from the statement
Input3
3 0 3
Output3
Noteis a simple basin between two equal walls
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.