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://bzwzjz.com/article/dcejdj.html