42. Trapping Rain Water --H ！！！！！老毛病，第一个方法不太对

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

A:

[解题思路]
对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
3. 再扫描一遍，求取容积并加和。

Mistakes:

****************扫两遍***************************

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n<=2)
            return 0;
        vector<int> maxLeft(n,0);
        for(int i = 1;i<n;i++){
            maxLeft[i] = max(maxLeft[i-1], height[i-1]);
        }
        int res = 0;
        int maxRight = height[n-1];
        for(int i = n-2;i>0;i--){
            res += max(0, (min(maxLeft[i], maxRight) - height[i]));
            maxRight = max(maxRight, height[i]);
        }
        return res;
    }
};

*******************第三遍**********为了面试的时候不出错， 还是扫3遍， 然后可以说再继续优化， 可以扫2遍就行********

class Solution {

public:

int trap(vector<int>& height) {

int n = height.size();

vector<int> L(n, 0), R(n, 0);

for (int i = 1; i < n; i++)

L[i] = max(L[i - 1], height[i - 1]);

for (int j = n - 2; j >= 0; j--)

R[j] = max(R[j + 1], height[j + 1]);

int total = 0;

for (int i = 0; i < n; i++)

total += max(0, min(R[i], L[i]) - height[i]);

return total;

}

};

Learned:
1： 尽量让自己的helper function 为private 。 阿三可能用这个来据你。