Trapping Rain Water

Problem Given an elevation map represented as an array of non-negative bar heights (each bar of width 1), compute how much rain water is trapped between the bars after it rains.

Input / Output

• Input: integer array height of bar heights.
• Output: total units of water trapped.

Constraints

• 1 <= n <= 2 * 10^4.
• 0 <= height[i].

Example

• [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
• [4,2,0,3,2,5] -> 9