Problem Statement

Trapping Rain Water You are given n non-negative integers height[0..n-1] describing an elevation map. The bar at index i has height height[i] and width 1 , and the bars stand side by side with no gaps. It rains until no more water can settle. Water is held above a column only if there is a bar at least as tall as the water on both sides of it; anything that spills past the two ends of the map runs off. Compute how much water the elevation map can trap after raining. Formally, the column at index i holds max(0, min(max(height[0..i]), max(height[i..n-1])) - height[i]) units of water, and the answer is the sum of that quantity over all i . Function Description Complete the function trap in the editor, with the following parameter: int height[n] : the heights of the bars, from left to right Return long : the total number of units of water trapped. Constraints n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 Input Format for Custom Testing Input from stdin will be pr