题目
给定 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
解法一（暴力法）
思路：在每个位置，分别向左和向右找雨水的边界，从而得到雨水在当前位置的深度，累加每个位置的深度即为所求。
- 对整个区域的每个位置进行计算
- 分别向左和向右寻找边界值，然后取得两个边界值的最小值，作为当前水量高度
- 累加所有坐标的水量
- 时间复杂度：O(n2)
- 空间复杂度：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;
}
解法二（动态规划）
思路：基于解法一进行优化，解法一每个位置都要遍历整个区间来寻找左右最大值，可以基于动态规划的思想，分别从左右两边开始寻找当前位置的左右方向的最大值，因此执行时间从N2变为2N。
- 申请临时空间，分别用于存储当前坐标，左右两边的最大值
- 从左边开始向右寻找每个左边能看到的最大值，右边同理
- 累加所有坐标的水量
- 时间复杂度：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;
}
解法三（双指针法）
思路：基于解法二进行优化，由于求出一个位置左右两边最大值后，仅使用其中较小的值，并舍弃较大一边的值，因此不必找到每个位置左右两边的最大值，而是只要找到左右两边最大值中较小的值即可。
使用两个指针，来标志左右两边的位置值，并不断向中间递进，如果坐标值大则右边指针一直向左边移动，反之亦然，每个位置计算时候都是左右两边的最大值中的较小值。
- 左边最大值从左向右移动，右边最大值从右向左移动，左右两个指针相遇后，循环结束
- 左边值如果大于右边，则计算右边当前储水量，并且右边指针向左移动，反之同理
- 分别记录两边的最大值，用于计算每个位置的储水量，储水量等于最大值减去当前值
- 时间复杂度：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;
}
