[LeetCode]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.

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!

思路：找到最大值及其位置pos。然后从左往右遍历到pos，再从右往左遍历到pos。

什么时候会加水呢？

遍历的时候记录最大值，也就是全局第二大的值，如果当前值比第二大的小，那么就会加水了，小多少就加多少。

加水是一列列加的。下图。

 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         if(height.size()<=2) return 0;
 5         int result=0;
 6         int pos=0,maxHeight=0;
 7         for(int i=0;i<height.size();i++)
 8         {
 9             if(height[i]>maxHeight)
10             {
11                 maxHeight = height[i];
12                 pos = i;
13             }
14         }
15         int cur_max = height[0];
16         for(int i=1;i<pos;i++)
17         {
18             cur_max = max(cur_max,height[i]);
19             result+=(cur_max-height[i]);
20         }
21         cur_max = height[height.size()-1];
22         for(int i=height.size()-2;i>pos;i--)
23         {
24             cur_max = max(cur_max,height[i]);
25             result+=(cur_max-height[i]);
26         }
27         return result;
28     }
29 };

其实不需要找到最大值也可以。按照寻找最大值的思路。移动第二大的值。思路和上面一样。代码简洁些。

 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         if(height.size()<=2) return 0;
 5         int result=0;
 6         int left=0,right=height.size()-1,secHeight=0;
 7         while(left<right)
 8         {
 9             if(height[left]<height[right])
10             {
11                 secHeight = max(height[left],secHeight);
12                 result+=(secHeight-height[left]);
13                 left++;
14             }
15             else
16             {
17                 secHeight = max(height[right],secHeight);
18                 result+=(secHeight-height[right]);
19                 right--;
20             }
21         }
22         return result;
23     }
24 };