【题解】【直方图】【Leetcode】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!

思路：

O(n) solution. for each bar, find the max height bar on the left and right. then for this bar it can hold min(max_left, max_right) - height

对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。

直方图的题还有Container With Most Water和Largest Rectangle in Histogram，还可以看看Maximal Rectangle，都很有意思

代码：

 1 int trap(int A[], int n) {
 2     if(n < 3) 
 3         return 0;    
 4     
 5     vector<int> maxRs(n);  
 6     int maxR = 0;
 7     for(int i = 0; i < n; i++){
 8         if(A[i] > maxR) 
 9             maxR = A[i];
10         maxRs[i] = maxR;
11     }
12     
13     int totalV = 0;
14     int maxL = 0;
15     for(int i = n-1; i >= 0; i--){
16         if(A[i] > maxL) 
17             maxL = A[i];
18         totalV += min(maxL, maxRs[i]) - A[i];
19     }
20     return totalV;
21 }