# 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: Code: