Trapped Volume Between Heights

You are given an array heights where heights[i] is the height of a vertical bar standing at position i. The bars stand side by side in a row and each one is 1 unit wide, so together they form an uneven skyline with dips between the taller bars.

Now pour water over the whole row. A dip holds water only if it has a taller bar on both sides, and fills to the height of the shorter of the two; water reaching either end runs off.

Return the total number of unit squares of water that stay behind.

For heights = [0,1,0,2,1,0,1,3,2,1,2,1] the answer is 6. Bars are # and trapped water is ~:

3 |                       #
2 |           #  ~  ~  ~  #  #  ~  #
1 |     #  ~  #  #  ~  #  #  #  #  #  #
  +------------------------------------
     0  1  2  3  4  5  6  7  8  9 10 11

Position 2 has a bar of height 1 on its left and a bar of height 2 on its right, so it fills to level 1 and holds 1 unit. Positions 4, 5 and 6 sit between the bar of height 2 at position 3 and the bar of height 3 at position 7, so they fill to level 2 and hold 1 + 2 + 1 = 4 units. Position 9 sits between the two bars of height 2 at positions 8 and 10, so it fills to level 2 and holds 1 unit. Every other position already reaches the level of its shorter flanking bar and holds nothing, so the total is 1 + 4 + 1 = 6.

Formally, let maxLeft(i) be the greatest height among positions 0 through i, and maxRight(i) the greatest height among positions i through n - 1. The water level above position i is min(maxLeft(i), maxRight(i)), so position i holds

max(0, min(maxLeft(i), maxRight(i)) - heights[i])

units of water, and the answer is that quantity summed over every position. The first and last positions always hold 0.

Examples

Example 1

Input: heights = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The row drawn above. Positions 2, 4, 5, 6 and 9 hold 1, 1, 2, 1 and
1 units of water; every other position holds none.

Example 2

Input: heights = [4,2,0,3,2,5]
Output: 9
Explanation: Positions 1 through 4 have the bar of height 4 at position 0 on
their left and the bar of height 5 at position 5 on their right, so they fill to
level 4. They hold 4-2, 4-0, 4-3 and 4-2 units, that is 2 + 4 + 1 + 2 = 9.