题解 | #NC28-接雨水问题#

/**
 * max water
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return long长整型
 */
/******************************************************************************
* 定义边界left和right，left是左边界，初值是0；right值右边界，初值是arrLen-1
* 定义i和j，i初始时为左边界left，j初始为右边界
* ①、++i向右遍历
*    arr[i]小于左边界说明可能有雨水，进行累加
*    arr[i]不小于左边界说明没雨水，更新左边界left值为i
* ②、--j向左遍历
*    arr[j]小于右边界说明可能有雨水，进行累加
*    arr[j]不小于右边界说明没雨水，更新右边界right值为j
* 使用while循环计算雨水总和，循环条件是i<j
*【当左边界arr[left]<arr[right]时，说明左侧有可能有雨水，进行①操作，否则进行②操作】
******************************************************************************/


long long maxWater(int* arr, int arrLen ) {
    // write code here
    int left = 0;//左边界
    int right = arrLen-1;//右边界
    long long water = 0;
    int i = left;//++i从左边界向右找，若arr[i]大于左边界arr[left]，将左边界值arr[left]更新为arr[i]
    int j = right;//--j从右边界向左找，若arr[j]大于左边界arr[left]，将左边界值arr[left]更新为arr[i]
    
    while(i < j)
    {
        //如果arr[left]小于arr[right]，说明左侧可能有雨水量
        if(arr[left] < arr[right])
        {
            //从左边界向右进行判断，如果右侧数值小于左边界，说明有雨水，进行相加
            if(arr[++i] < arr[left])
                water += arr[left]-arr[i];
            else
                //从左边界向右找，一直找到不小于左边界的值，更新左边界
                left = i;
        }
        //如果arr[left]不小于arr[right]，说明右侧可能有雨水量
        else
        {
            //从右边界向左进行判断，如果左侧数值小于右边界，说明有雨水，进行相加
            if(arr[--j] < arr[right])
                water += arr[right]-arr[j];
            else
                //从右边界向左找，一直找到不小于右边界的值，更新右边界
                right = j;
        }
    }
    return water;
}