Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.
Each position can trap water based on the tallest walls to its left and right.
Examples
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Input: height = [4,2,0,3,2,5] Output: 9
Constraints
- 1 <= height.length <= 20,000
- 0 <= height[i] <= 100,000