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) 相同或更短(即 \leq h[i]≤h[i] ); 方法二:两个for循环的暴力法:时间复杂度为O(n2),对于某些题可能会有时间超限。 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
*思路:*首先两个指针分别指向头和尾,然后判断两个指针的值,哪个更小,就移动哪个指针(因为如果移动大的那个,永远不可能得到更大的容积)。证明过程如下:
假设状态 S(i, j)S(i,j) 下 h[i]< h[j]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;
}
思想:找出所有边的组合,再找出大容量//思路:比较简单:就是任意找两根线,求出容水量(取大值)
int maxArea(int* height, int heightSize){int sum=0,min,s,i,j;
for(i=0;i
网站题目:c语言实现-盛最多水的容器(两种方法)-创新互联
分享URL:http://scjbc.cn/article/dcejdj.html