题目描述
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
注： 上面蓝色部分面积是样例1中能够接到雨水的部分。
输入格式
第一行是一个正整数n,n表示柱子的数量。
第二行有n用空格隔开的正整数，第height[i]个数字表示第i个柱子的高度。
输出格式
输出一个整数
样例 #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]<=1*10^5
题目思路
该题的想法是枚举每一个柱子的上方能接多少水，由于每一个柱子都会枚举到所以并不用考虑周围。
至于求上方能接多少水的方法，我们使用前缀和后缀数组来快速求解。
那么本题就非常简单了。
核心代码
求前缀和后缀数组部分
vector<int> prefixMax(const vector<int>& arr)
{
vector<int> prefix(arr.size());
prefix[0]=arr[0];
for(int i=1;i<arr.size();i++){
prefix[i]=max(prefix[i-1],arr[i]);
}
return prefix;
}
vector<int> suffixMax(const vector<int>& arr)
{
vector<int> suffix(arr.size());
suffix[arr.size()-1]=arr[arr.size()-1];
for(int i=arr.size()-2; i>=0;i--){
suffix[i]=max(suffix[i+1],arr[i]);
}
return suffix;
}
枚举部分
for(int i=0;i<n;i++)
{
int min_=min(prefix[i],suffix[i]);
ret+=min_-arr[i];
}