Trapping Rain Water

You get an array height. Each number is the height of a bar, and every bar is 1 unit wide.

When it rains, water fills the gaps between taller bars. Return how many units of water are trapped.

Example 1:

Input: height = [2,0,3,1,0,2,4,0,1]
Output: 9
Explanation: The blue squares are the water:
2 units over the first 0,
6 units between the 3 and the 4,
1 unit over the last 0.
In total, 2 + 6 + 1 = 9.

Example 2:

Input: height = [5,1,1,3]
Output: 4
Explanation: The water rises to 3, the shorter of the two outer bars.
That is 2 units above each 1.

Example 3:

Input: height = [1,2,3,2,1]
Output: 0
Explanation: No bar has a taller bar on both sides, so no water stays.

Constraints:

• 1 to 30,000 bars.
• Each height is a whole number from 0 to 10,000.