Trapping Rain Water

Problem

Given non-negative heights representing an elevation map (each bar width 1), compute how much water it can trap after raining.

Example

height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Constraints

• 1 ≤ n ≤ 2 × 10^4

Expected

Two-pointer O(n) time, O(1) space. Be ready to explain why the two-pointer invariant is correct.