ArrayTwo PointersStackDynamic Programming
Each number is the height of a bar of width 1. After it rains, water collects in the dips between bars. Compute how many units of water are trapped in total.
Input
Line 1: n. Line 2: n non-negative heights.
Output
Print the total units of trapped water.
Constraints
1 <= n <= 10^5 0 <= height <= 10^5
Example 1
Input
12 0 1 0 2 1 0 1 3 2 1 2 1
Output
6
6 units of water collect in the dips.