欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

#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;
}