Trapping Rain Water

The heights of n bars of width 1 form an elevation map. After it rains, how much water is trapped between the bars?

Above each bar, the water level is min(highest bar to its left, highest bar to its right) (counting the bar itself), and the bar holds level − height units.

Input:

• line 1: n
• line 2: n heights

Output: the total trapped water (it can need a 64-bit integer).

Constraints: 1 ≤ n ≤ 2·10⁵, 0 ≤ h[i] ≤ 10⁵.

Think about it: prefix/suffix maximum arrays give O(n) with O(n) memory. Two pointers give O(n) with O(1) memory: always move the side with the lower wall.