3种方法： 计算接最多的雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

<center><img src="/img/alg/20200404104541992.png“></center>

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

---

解法一（暴力法）

思路：在每个位置，分别向左和向右找雨水的边界，从而得到雨水在当前位置的深度，累加每个位置的深度即为所求。

1. 对整个区域的每个位置进行计算
2. 分别向左和向右寻找边界值，然后取得两个边界值的最小值，作为当前水量高度
3. 累加所有坐标的水量

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

//author： suoxd123@126.com
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx, rightVal, leftIdx, leftVal;
    for(int k=0; k<heightSize; k++){
        rightIdx = k;
        rightVal = height[k];
        leftIdx = k;
        leftVal = height[k];
        for(int i=0; i<k; i++){//向左找最大值
            if(height[i] > leftVal){
                leftVal = height[i];
                leftIdx = i;
            }
        }
        for(int i=k+1; i<heightSize; i++){//向右找最大值
            if(height[i] > rightVal){
                rightVal = height[i];
                rightIdx = i;
            }
        }
        cnt += (leftVal> rightVal?rightVal:leftVal) - height[k];
    }
    return cnt;
}

---

解法二（动态规划）

思路：基于解法一进行优化，解法一每个位置都要遍历整个区间来寻找左右最大值，可以基于动态规划的思想，分别从左右两边开始寻找当前位置的左右方向的最大值，因此执行时间从N²变为2N。

1. 申请临时空间，分别用于存储当前坐标，左右两边的最大值
2. 从左边开始向右寻找每个左边能看到的最大值，右边同理
3. 累加所有坐标的水量

• 时间复杂度：O(n)
• 空间复杂度：O(n)

//author： suoxd123@126.com
int trap(int* height, int heightSize){
    if(heightSize == 0) return 0;
    int cnt = 0, *leftMax, *rightMax;//临时变量保持各位置的左右最大值
    leftMax = (int *)malloc(sizeof(int)*heightSize);
    rightMax = (int *)malloc(sizeof(int)*heightSize);
    memset(leftMax,0,heightSize);
    memset(rightMax,0,heightSize);
    leftMax[0] = height[0];
    for(int i=1;i<heightSize;i++){//左边最大值
        leftMax[i] = leftMax[i-1] > height[i]?leftMax[i-1]:height[i];
    }
    rightMax[heightSize - 1] = height[heightSize - 1];
    for(int i=heightSize - 2;i>=0;i--){//右边最大值
        rightMax[i] = rightMax[i+1] > height[i]?rightMax[i+1]:height[i];
    }
    for(int i=0; i<heightSize; i++){
        cnt += (leftMax[i]> rightMax[i]?rightMax[i]:leftMax[i]) - height[i];
    }
    free(leftMax)
    free(rightMax)    
    return cnt;
}

---

解法三（双指针法）

思路：基于解法二进行优化，由于求出一个位置左右两边最大值后，仅使用其中较小的值，并舍弃较大一边的值，因此不必找到每个位置左右两边的最大值，而是只要找到左右两边最大值中较小的值即可。

使用两个指针，来标志左右两边的位置值，并不断向中间递进，如果坐标值大则右边指针一直向左边移动，反之亦然，每个位置计算时候都是左右两边的最大值中的较小值。

1. 左边最大值从左向右移动，右边最大值从右向左移动，左右两个指针相遇后，循环结束
2. 左边值如果大于右边，则计算右边当前储水量，并且右边指针向左移动，反之同理
3. 分别记录两边的最大值，用于计算每个位置的储水量，储水量等于最大值减去当前值

• 时间复杂度：O(n)
• 空间复杂度：O(1)

//author： suoxd123@126.com
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx = heightSize - 1, rightVal = 0, leftIdx = 0, leftVal = 0;
    while(leftIdx <= rightIdx){
        if(leftVal < rightVal){//最大值在右边
            if(height[leftIdx] > leftVal){//存储左边新的最大值
                leftVal = height[leftIdx];
            }
            else{//基于左边值计算储水量
                cnt += leftVal - height[leftIdx];
            }
            leftIdx ++;
        }
        else{
            if(height[rightIdx] > rightVal){//记录右边最大值
                rightVal = height[rightIdx];
            }
            else{
                cnt += rightVal - height[rightIdx];
                rightIdx --;
            }
        }
    }
    return cnt;
}

---