15725 接雨水 题解

经验分享区
1

\Large 也是非常勤奋的就来写题解了好吧
其实是因为赵哥不会写

题目描述

接雨水

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

输入格式

第一行是一个正整数 n ， n 表示柱子的数量。

第二行有nn用空格隔开的正整数，第 height[i] 个数字表示第ii个柱子的高度。

输出格式

输出一个整数

样例 #1

样例输入 #1

12
0 1 0 2 1 0 1 3 2 1 2 1

样例输出 #1

6

样例 #2

样例输入 #2

6
4 2 0 3 2 5

样例输出 #2

9

提示

1<= n <=2∗10^4

0<=height[i]<=10^5

思路

不难发现，一个柱子积水的体积取决于它左右两边最高的柱子高度。

设左边柱子最高为 Max_l ，右边柱子最高为 Max_r 。
则此柱子积水的高度为 min(Max_l,Max_r)-height_i 。
前提是 min(Max_l,Max_r) 一定严格大于 height_i 。

所以，我们只需求出每个 height_i 的 Max_l 和 Max_r 就行了。

参考部分代码：

 int lmx=a[1],rmx=a[n];
 for(int i=2;i<=n;i++){//算出Max_l
    f[i][0]=lmx;
    lmx=max(lmx,a[i]);
}
for(int i=n-1;i>0;i--){//算出Max_r
    f[i][1]=rmx;
    rmx=max(rmx,a[i]);
}
for(int i=2;i<n;i++){//求出水量
    if(min(f[i][0],f[i][1])>a[i]){
        cnt+=min(f[i][0],f[i][1])-a[i];
    }
}

加上输入，时间复杂度为 O(4n) 其实可以是3n，但我懒，是 O(n) 级别的，完全可以A掉。

1 个赞