//单调栈解法
int trap(int* height, int heightSize){
    int stack[heightSize];
    int area = 0, top = -1;
    for (int i = 0; i < heightSize; i++) {
        while ( top > 0 && height[i] > height[stack[top]]) {
            area+=(fmin(height[i], height[stack[top-1]]) - height[stack[top]]) * (i - stack[top-1] - 1);
            top--;
        }
        if (top == 0 && height[i] > height[stack[top]]) {
            stack[top] = i;
            continue;
        }
        top++;
        stack[top] = i;
    }
    return area;
}

/*正向计算每个池塘的容积，再反向计算每个池塘的容积
int trap(int* height, int heightSize){
    int left = 0, right = 0, tmp_area = 0, ret_area = 0;
    while (++right < heightSize) {
        if (height[right] < height[left]) {
            tmp_area+=height[right];
        }
        else {
            ret_area+=((right-left-1)*height[left] - tmp_area);
            tmp_area = 0;
            left = right;
        }
    }

    tmp_area = 0;
    int tail = heightSize - 1;
    right--;
    while (--right >= left) {
        if (height[right] < height[tail]) {
            tmp_area+=height[right];
        }
        else {
            ret_area+=((tail-right-1)*height[tail] - tmp_area);
            tmp_area = 0;
            tail = right;
        }
    }
    return ret_area;
}
*/