c语言实现-盛最多水的容器(两种方法)-创新互联

在这里插入图片描述

成都创新互联服务项目包括金寨网站建设、金寨网站制作、金寨网页制作以及金寨网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,金寨网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到金寨省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

题目描述:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的大值为 49。

方法一:双指针法:
*思路:*首先两个指针分别指向头和尾,然后判断两个指针的值,哪个更小,就移动哪个指针(因为如果移动大的那个,永远不可能得到更大的容积)。证明过程如下:
假设状态 S(i, j)S(i,j) 下 h[i]< h[j]h[i]

短板高度:相比 S(i, j)S(i,j) 相同或更短(即 \leq h[i]≤h[i] );
底边宽度:相比 S(i, j)S(i,j) 更短;
因此,每轮向内移动短板,所有消去的状态都 不会导致面积大值丢失

int maxArea(int* height, int heightSize){ //利用双指针法,O(n)的时间复杂度符合题意
    int left=0,right=heightSize-1,sum=0,s;
    while(left!=right)
    {if(height[left]>height[right])
        {s=height[right]*(right-left);
            right=right-1;
        }
        else
        {s=height[left]*(right-left);
            left=left+1;
        }
        if(s>sum)
            sum=s;
    }
    return sum;
}

方法二:两个for循环的暴力法:时间复杂度为O(n2),对于某些题可能会有时间超限。
思想:找出所有边的组合,再找出大容量

//思路:比较简单:就是任意找两根线,求出容水量(取大值)
    int maxArea(int* height, int heightSize){int sum=0,min,s,i,j;
    for(i=0;ifor(j=i;jif(height[i]min=height[i];
            }
            else
            {min=height[j];
            }
            s=min*(j-i);
            if(s>sum)
            {sum=s;
            }
        }
    }
    return sum;
    }

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站题目:c语言实现-盛最多水的容器(两种方法)-创新互联
分享URL:http://scjbc.cn/article/dcejdj.html

其他资讯