美文网首页刷题总结
谈一道LeetCode——接雨水

谈一道LeetCode——接雨水

作者: 思想永不平凡 | 来源:发表于2019-11-07 22:52 被阅读0次

    今天写了一道LeetCode,虽然题目并不难,但是过程没有想象中那样简单,经历了一波三折,有什么曲折呢,一起来看看吧!



    题目介绍

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。


    图片.png

    上面是由数组 [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

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/trapping-rain-water

    题目分析

    由题意和图可知,此题说通俗一点就是计算矩形的面积。
    简单来说就是,一层层地计算这一层的矩形面积,在计算本层的时候,应该注意没有方块以及之前被覆盖的矩形区域。
    比如说,高度为1的矩形被统计过后,下一次统计时,第一层即使是空的,也不能被纳入该次计算中。

    解题

    本人写了第一份程序,测试了一些样例后,没有问题,提交了。
    下面展示下程序,鉴于本人代码水平不高,还请各位大佬多多指教......

    class Solution {
    public:
        int trap(vector<int>& height) {
            int area=0;
            int temp=0;
            if(height.size()==0){
                return 0;
            }else{
                int max=0,max_index=0;
                for(int i=0;i<height.size();i++){
                    if(height[i]>max){
                        max=height[i];
                        max_index=i;
                    }
                }
                for(int i=1;i<=max;i++){
                    int start=find_start(height,i);
                    int end=find_end(height,i);
                    if(start!=-1&&end!=-1){
                        for(int j=start;j<=end;j++){
                            if(i>=height[j]){
                                if(height[j]>temp){
                                    area+=(i-height[j]);
                                }else{
                                    area+=(i-temp);
                                }
                            }
                        }
                        temp=i;
                    }
                }
                return area;
            }
        }
        int find_end(vector<int>& height,int num){
            int locate=-1;
            for(int i=height.size()-1;i>=0;i--){
                if(height[i]>=num){
                    locate=i;
                    break;
                }
            }
            return locate;
        }
        int find_start(vector<int>& height,int num){
            int locate=-1;
            for(int i=0;i<height.size();i++){
                if(height[i]>=num){
                    locate=i;
                    break;
                }
            }
            return locate;
        }
    };
    

    测试了很多样例,都通过了,但是系统却未通过。一看原因,如下图

    图片.png

    很简单,最后一个样例太大了,导致程序在这个样例上超时了。
    再回到程序中,发现有些循环并非需要这样写,可优化的地方很多
    基于此,重新写了一份,这次通过了,下面展示下程序

    class Solution {
    public:
        int trap(vector<int>& height) {
            int area=0;
            int length=height.size();
            int max_l=0,max_r=0;
            if(length==0){
                return 0;
            }else{
                for(int i=1;i<length-1;i++){
                    max_l=0,max_r=0;
                    for(int j=i;j>=0;j--){
                        max_l=max_l>height[j]?max_l:height[j];
                    }
                    for(int j=i;j<length;j++){
                        max_r=max_r>height[j]?max_r:height[j];
                    }
                    area+=(max_l<max_r?max_l:max_r)-height[i];
                }
                return area;
            }
        }
    };
    

    这次倒是成功通过了,结果如下:

    图片.png

    但是发现时间方面还是有很大优化的空间,分析上述程序可以发现

    for(int i=1;i<length-1;i++){
      /*
      *
      */
    }
    

    这个循环里面两个找左右最大小值时,两个循环每次都会被执行,实际上,我们完全可以设置两个vector预先将左边和右边的最大值提前存储起来,也许会多花一些空间,但是时间消耗会明显减少。
    下面展示改进后的程序:

    class Solution {
    public:
        int trap(vector<int>& height) {
            int length=height.size();
            if(length==0){
                return 0;
            }else{
                int area=0;
                int temp=0;
                vector<int> max_start(length),max_end(length);
                max_start[0]=height[0];
                max_end[length-1]=height[length-1];
                for(int i=1;i<length;i++){
                    max_start[i]=max_start[i-1]>height[i]?max_start[i-1]:height[i];
                }
                for(int i=length-2;i>=0;i--){
                    max_end[i]=max_end[i+1]>height[i]?max_end[i+1]:height[i];
                }
                for(int i=1;i<length-1;i++){
                    temp=max_start[i]<max_end[i]?max_start[i]:max_end[i];
                    area+=temp-height[i];
                }
                return area;
            }
        }
    };
    

    提交结果如下图所示:

    图片.png

    效果显著!!!

    总结

    虽然此题并不难,但是仔细去品味还是有不少可以推敲的。
    从一开始得出正确答案,而面对大样例时,会超时。
    之后进行改进,去掉了一些不必要的循环,通过,但是耗时多。
    最后,从空间角度出发,开辟两个vector,大大减少了程序的运行时间。

    得到预期的结果也许不难,但是能够将所有的情况考虑周全却不容易。即使得到了正确结果,很多时候,不妨先别着急庆祝,看看是否有值得优化的地方,多一些思考,多一些实践,自己的进步将会十分明显!!!

    相关文章

      网友评论

        本文标题:谈一道LeetCode——接雨水

        本文链接:https://www.haomeiwen.com/subject/upsbbctx.html