Given

*n*non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,

Given

Given

`[0,1,0,2,1,0,1,3,2,1,2,1]`

, return `6`

.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

**Thanks Marcos**for contributing this image!
Solution: DP

To calculate the total volume is to calculate volumes can hold at each position.

To calculate how many volumes can hold at each position is to calculate it's right bound height and right bound height

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so, use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record highest height bound can get from left to current and highest height bound can get from right to current

HigehstLeftSideHeight so far from giving example, should be 0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold