Trapping Rain Water

一. 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.

Difficulty:Hard

TIME：20MIN

解法

记得之前做过一道题Container With Most Water，如果有那道题的经验，那么这道题也不难解决。

既然知道积累雨水是基于比较小的边，那么我们从比较小的边开始遍历，直到找到另一个长度大于等于它的边，那么就可以着手计算这个区域内的雨水了（其实采用累加计算，找到长度大于等于它的边，就已经计算了好了这个区域内的雨水）

int trap(vector<int>& height) { if(height.size() < 3) return 0; int result = 0; int left = 0,right = height.size() - 1; int maxLeft = height[left], maxRight = height[right]; while(left <= right) { if(maxLeft >= maxRight) { //从边长比较小的边开始遍历（保证会遇到边长比较大的边） if(height[right] >= maxRight) maxRight = height[right]; //重置边长 else result += maxRight - height[right]; //累加雨水量 right--; } else { if(height[left] >= maxLeft) maxLeft = height[left]; else result += maxLeft - height[left]; left++; } } return result; }

代码的时间复杂度为 O(n) 。