#leetcode刷题之路42-接雨水
程序员文章站
2022-10-06 13:16:09
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。 示例:输入: [0,1,0, ......
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
思路:自左向右查找,以begin找到非零的数字开始,end=beigin+1向后找,可以构成凹槽时则计算,不可以时九八begin位置的高度减1,然后就是for循环不断执行
#include <iostream> #include <vector> using namespace std; int trap(vector<int>& height) { if(height.size()==1||height.size()==2||height.size()==0) return 0; long begin=0,end=0,count=0,dis=0,i=0; int ans=0; while(height[i]==0) { begin++; i++; } //cout<<"begin="<<begin<<endl; while(end<height.size())//确定begin,end { end=begin+1; if(end==height.size()) break; for(;end<height.size();end++)//找end { if(height[begin]<=height[end]) break;//判断是否可以构成一个凹槽 } dis=end-begin-1;//距离 //cout<<"end="<<end<<endl; //cout<<"dis="<<dis<<endl; if(end!=height.size())//构成凹槽成功 { for(int i=begin+1;i<end;i++) { count+=height[i]; } ans+=dis*height[begin]-count;//加入面积 //cout<<"ans="<<ans<<endl; begin=end; //cout<<"begin="<<begin<<endl; dis=0; count=0; } else { //cout<<"res1="<<height[begin]<<endl; height[begin]-=1; //cout<<"res2="<<height[begin]<<endl; end=begin; } } return ans; } int main() { vector<int> a={0,1,0,2,1,0,1,3,2,1,2,1}; int ans=trap(a); std::cout <<ans<< std::endl; return 0; }