本文共 3082 字，大约阅读时间需要 10 分钟。

题目

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

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

示例:

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

解法一（暴力法）

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

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

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

//author： suoxd123@126.comint 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.comint 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.comint 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;}