# Leetcode 42 - ðŸ’¦ Trapping rain water ðŸ’¦

`Note:`

- To find how many water some cols can trap, we need to know the
`highest walls`

on both side. - How can we quickly get a col that is higher than current col on the
`left`

or`right`

? - A
`decreasing monotonic stack`

! Only store`indexes`

in the stack. - When the current
`height[i]`

is higher than the`top`

of the stack. We need to pop it out`stack.pop()`

. - The question is, how wide does the
`top`

extend to both side? - There is one thing that we can be sure:
`Area between cols in stack have been fill out with water if there are gaps between them`

.- All other cols in
`height`

between two adjacent elements in`stack`

are shorter than those two. We can def trap some water there.

- So, the
`WDITH = i - newTop - 1`

, which is cols of indexes`4, 5, 6, 7, 8`

. - The
`HEIGHT = min(height[newTop], height[i]) - height[oldTop]`

. - Like I showed here .

`Question:`

Given `n`

non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining

`Example:`

1 | Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] |

`Code:`

1 | /** |