LeetCode42 Trapping Rain Water*

LeetCode42 Trapping Rain Water**

题目地址：https://leetcode.com/problems/trapping-rain-water/

这道题关键点是是两边往中间遍历，记录当前第二高点secHeight，然后利用这个第二高点减去当前历经的柱子，剩下就装水容量了。
为什么是第二高点？因为两边比较，最高的点不用动，只移动第二高点。

这也是阿里2015实习生招聘附加题第三题

class Solution {
public:
    int trap(int A[], int n) {
        int secHeight = 0;
        int left = 0;
        int right = n-1;
        int area = 0;
        while(left < right){
            if(A[left] < A[right]){
                secHeight = max(A[left], secHeight);    // 找到次最高点
                area += secHeight - A[left];
                left ++;
            }else{
                secHeight = max(A[right], secHeight);
                area += secHeight - A[right];
                right --;
            }
            
        }
        return area;
        
    }
};