Leetcode - 42.Trapping Rain Water

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 [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!

思路

通过上图可以看出本题的解题思路：

1. 从左往右计算当前的最大高度，保存到数组left_max中；
2. 从右往左计算当前的最大高度，保存到数组right_max中；
3. 遍历高度数组，并计算结果：
   ans += min(max_left[i],max_right[i])−height[i]

代码路径

原题路径