接雨水问题

/**
 * max water
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return long长整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
//双指针法
int min(int a, int b)
{
    return a < b? a:b;
}
long long maxWater(int* arr, int arrLen ) {
    // write code here
    int sum = 0;
    int left = 0, right = 0;
    int count = 0;//统计指针之间的格子个数
    int max = 0, max_pos;//记录右指针远离左指针过程中出现的最大值及坐标
    while(left < arrLen - 1)
    {
        count = 0;
        max = 0;
        max_pos = arrLen - 1;
        //每次开始时左指针遇到非降时就直接向前移动
        while(*(arr + left) <= *(arr + left + 1))
        {
            left ++;
        }
        //右指针一直移动到不低于左指针的位置
        right = left + 1;
        while(*(arr + right) < *(arr + left)  && right < arrLen - 1)
        {
            //最大值的记录
            if(*(arr + right) > max)
            {
                max = *(arr + right);
                max_pos = right;
            }
            count +=  *(arr + right);
            right ++;
        }
        //如果右指针直接移动动了数组边界
        if(right == arrLen - 1) 
        {
            //将它与最大值作比较从而根据情况作下一步判断
            if(*(arr + right) >= max)//理想情况，如果最大值在数组边界处
            {
                sum += (right - left - 1) * min(*(arr + left),*(arr + right)) - count;
                break;
            }
            else
            {    //否则right指针回溯到最大值所在地方
                for(right -= 1;right >= max_pos; right --)
                {
                    count -= *(arr + right);
                }
                right = max_pos;
            }
        }
        sum += (right - left - 1) * min(*(arr + left),*(arr + right)) - count;
        left = right;
    }
    return sum;
}

/**
 * max water
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return long长整型
 */
/*这个题可以这样来理解，从“第一个”开始，我们需要找到一个比它高的“木板”，
这样就能存储下雨水，如果没有比它高的，那就找到除它之外最高的，与它构成一个凹槽。
计算出这个凹槽的储水量。
然后再以刚找到的“木板”当“第一个”，重复上述操作。
*/

long long maxWater(int* arr, int arrLen) {
    // write code here
    int i = 0;
    int tmp = 0;//用来记忆遍历数组的最大值
    int j = 0;
    long long num = 0;//雨水数
    int pos = -1;//用来记住遍历数组最大值的位置
    while (i<arrLen-1)
    {
        j = i + 1;//为什么不放入循环呢？因为如果放入，第二次使用循环时这个语句就不会被使用。
        for ( ; j<arrLen; j++)//寻找“第一个”后面最高的
        {
 
            if (arr[j]>tmp)//把过程中大的值记录下来，这样如果后面找不到比“第一个”高的木板时，我们不必再重头找除“第一个”之外最高的木板了。
            {
                tmp = arr[j];
                pos = j;//记录下位置
            }
            if (arr[j] >= arr[i])
            {
                for (int n = i; n<j; n++)//找到后计算储水量。
                {
                    num = num + arr[i] - arr[n];
                    tmp = 0;
                }
                i = j;
                break;
            }
        }
        if (j >= arrLen)//这说明没有找到比“第一个”高的
        {
            j = i + 1;
            for (; j<pos; j++)
            {
                num = num + tmp - arr[j];//计算储水量时以tmp为标准。
            }
            i = pos;
            tmp = 0;
        }
    }
    return num;
}