653. Trapping Rain Water

Given non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining. The input is JSON {height}.

Input: JSON {height}.

Output: Integer — the total trapped water.

Examples

Input: {"height":[0,1,0,2,1,0,1,3,2,1,2,1]}
Output: 6
Explanation: Six units of water are trapped.

Input: {"height":[4,2,0,3,2,5]}
Output: 9
Explanation: Nine units trapped.

Input: {"height":[3]}
Output: 0
Explanation: No basin.

Constraints

• 0<=n<=10^5
• 0<=height[i]<=10^5

Asked by