题目描述
接雨水
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
注： 上面蓝色部分面积是样例1中能够接到雨水的部分。
输入格式
第一行是一个正整数nn,nn表示柱子的数量。
第二行有nn用空格隔开的正整数，第height[i]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
这个题做法比较简单。
我们就只用考虑每根柱子上的积水就可以了
（找到两边最高柱子，取最小的减去当前柱子高度即为当前柱子上的积水）
//pre是前缀和，suf是后缀，ans为答案
for(int i=0;i<n;i++){
if(min(pre[i],suf[i])<=a[i])continue;//判断是否两边最高柱子是否比当前高或一样高，每当前高跳过，即为不能积水
ans+=(min(pre[i],suf[i])-a[i]);
}
//核心代码