LeetCode: Trapping Rain Water

思路分析

这种区间的问题一般都需要用到左右依赖信息，比如这里是对于最大值的依赖，所以一般都是要用左右遍历记录信息的方式来求解。考虑每一个位置上面最大的存水量，它完全取决于它左边最高的位置，与右边最高的位置的最小值，亦即最短板。这样，我们从左往右遍历记录每个位置左边的最大值，再从右往左遍历记录每个位置右边的最大值，最后从头遍历一遍进行计算即可。很有意思的题目，有各种变体版本。

代码

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    int trap(int A[], int n) {
        int * Left = new int[n];
        int * Right = new int[n];
        int _max = 0;
        rep(i, n) {
            Left[i] = _max;
            _max = max(A[i], _max);
        }
        _max = 0;
        rev(i, n) {
            Right[i] = _max;
            _max = max(A[i], _max);
        }
        int ans = 0;
        rep(i, n) {
            ans += max(0, min(Left[i], Right[i]) - A[i]);
        }
        return ans;
    }
};