[leetcode_42] Trapping Rain Water

根据题目要求，求出灌入水的多少。
先找出某段中的比两边界较小值要大的最大值。如果存在该值，将问题拆分为左+最大值的index和最大值的index+右。
如果不存在该最大值，表示两个边界都比中间的大，灌水求和即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
public:
    int sum;
    void WaterStep(int A[],int left,int right) {
        int min = A[left] > A[right] ? A[right] : A[left];
        int max = min;
        int index = -1;
        for(int i = left+1; i < right; i++) {
            if(A[i] > max) {
                index = i;
                max = A[i];
            }
        }
        if(index == -1) {
            for(int i = left+1; i < right; i++)
                sum += min - A[i];
        }
        else {
            WaterStep(A, left, index);
            WaterStep(A, index, right);
        }
    }
    int trap(int A[], int n) {
        sum = 0;
        WaterStep(A, 0, n-1);
        return sum;
    }
};