\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掉。