给定 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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604575.html