LeetCode 题解（14）: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!

题解：

规律：每一个位置的储水量取决于该位置的 Left Largest Height (LLH) 和 Right Largest Height (RLH)，对于位置i，

若A[i] < min(LLH[i], RLH[i])，则该点储水量为min(LLH[i], RLH[i])-A[i]，

否则若A[i] >= min(LLH[i], RLH[i])，则该点的储水量为0。

从左至右扫描数组获得LLH[i]，从右至左边求RLH[i]边计算储水量。

需要额外O(n)存储空间，时间复杂度O(2n)=O(n)。

class Solution {
public:
    int trap(int A[], int n) {
        int* leftMaxHeight = new int[n];
        int leftMaxH = 0;
        for(int i = 0; i < n; i++)
        {
            leftMaxHeight[i] = leftMaxH;
            if(A[i] > leftMaxH)
                leftMaxH = A[i];
        }
        int rightMaxH = 0;
        int sum = 0;
        for(int j = n - 1; j >= 0; j--)
        {
            if(A[j] < FindMin(rightMaxH, leftMaxHeight[j]))
                sum += FindMin(rightMaxH, leftMaxHeight[j]) - A[j];
            if(A[j] > rightMaxH)
                rightMaxH = A[j];
        }
        return sum;
    }
    
    int static FindMin( int a, int b)
    {
        if(a <= b)
            return a;
        else 
            return b;
    }
};