【每日一题C】接雨水

ゝ一世哀愁。 2023-10-11 17:36 169阅读 0赞

**题目描述：**

![5928bf1024fe4f76ae78d310cd456ea1.png][]

**思路分析：**

1、当柱子数小于3时，接不到雨水；

2、每根柱子接到的雨水量跟其左最高柱子、右最高柱子、其本身高度有关，跟据木桶效应选其左最高柱子、右最高柱子的最小柱子，该柱接水量为此最小柱子减去其本身柱高，若非正数说明该柱无法接水；

3、通过循环选出每柱的左最高柱子和右最高柱子。

**代码展示：**

#include <stdio.h>
    int trap(int* height, int heightSize){
        if(heightSize<3) return 0;
        int left[heightSize],right[heightSize],sum=0;
        for(int i=1;i<heightSize-1;i++){
            left[i]=height[0];
            for(int j=1;j<i;j++){//i位置的左侧
            if(left[i]<height[j]) left[i]=height[j];//找出左侧最高柱子
            }
            right[i]=height[i+1];
            for(int j=i+2;j<heightSize;j++){//i位置的右侧
            if(right[i]<height[j]) right[i]=height[j];//找出右侧最高柱子
            }
        }
        for(int i=1;i<heightSize-1;i++){
            int h=left[i]<right[i]?left[i]:right[i];//左右最低柱
        if((h-height[i])>0)
            sum=sum+h-height[i];   
        }
        return sum;
    }
    int main(void) {
      int a[12]={0,1,0,2,1,0,1,3,2,1,2,1};
      int i=trap(a,12);
      printf("%d",i);
      return 0;
    }

运行结果：

**编程工具：**

分享一个实用的C语言编程网址：[https://lightly.teamcode.com/dashboard][https_lightly.teamcode.com_dashboard]

**参考链接：**

[https://blog.csdn.net/qq610736355/article/details/105145442][https_blog.csdn.net_qq610736355_article_details_105145442]

[5928bf1024fe4f76ae78d310cd456ea1.png]: https://img-blog.csdnimg.cn/5928bf1024fe4f76ae78d310cd456ea1.png
[https_lightly.teamcode.com_dashboard]: https://lightly.teamcode.com/dashboard
[https_blog.csdn.net_qq610736355_article_details_105145442]: https://blog.csdn.net/qq610736355/article/details/105145442