题解 | #接雨水问题#

/**
递归就完事啦：
	先判断整个数组区域是不是一整个连续接雨水的区域（即数组中的值小于数组中的左右边界）。
	是的话计算并累加雨水的量。
	不是则找出区域中间最大的值作为分割点，判断这个点两侧是否为连续接雨水的区域。
 */
#include <stdbool.h>
static long long count = 0;

void countRain(int* arr, int l, int r) {
    int tmp = arr[l] < arr[r] ? arr[l] : arr[r];
    for (int i = l + 1; i < r; i++) {
        count += (tmp - arr[i] > 0 ? tmp - arr[i] : 0);
    }
}
int getMaxInArr(int* arr, int l, int r) {
    int max = l + 1;
    if (r - l == 1) {
        return arr[r] > arr[l] ? arr[r] : arr[l];
    }
    for (int i = l + 1; i < r; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
}
bool isRainArea(int* arr, int l, int r) {
    int tmp = 0;
    if (arr[l] == 1 && arr[r] == 1) {
        return true;
    }
    int minSide = (arr[l] < arr[r] ? arr[l] : arr[r]);
    for (int i = l + 1; i < r; i++) {
        tmp = arr[i];
        if (tmp >= minSide) {
            return false;
        }
    }
    return true;
}
void countrAea(int* arr, int l, int r) {
    if (l == r) {
        return;
    }
    if (isRainArea(arr, l, r)) {
        countRain(arr, l, r);
    } else {
        int max = getMaxInArr(arr, l, r);
        countrAea(arr, l, max);
        countrAea(arr, max, r);
    }
}
long long maxWater(int* arr, int arrLen ) {
    countrAea(arr, 0, arrLen - 1);
    return count;

}