力扣-盛最多水的容器（双指针）

力扣-盛最多水的容器（双指针）

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器

代码：

int maxArea(int* height, int heightSize){
    int i,j=heightSize,max,h;
    max=height[0]>height[j-1]?(j-1)*height[j-1]:(j-1)*height[0];//给max赋初值
    for(i=1;i<=heightSize;i++)//左指针遍历整个数组
    {
        for(j=heightSize;j>i;j--)//右指针遍历从[n-1,i-1]的数组
        {
            h=height[i-1]>height[j-1]?(j-i)*height[j-1]:(j-i)*height[i-1];//h取此时长方形的面积
            if(max 
 
但是！！！
 
这样写有一个坏处，会超时！！！
 
 
 
 
所以进行了一下改进，时间复杂度变成了O(n)
 
int maxArea(int* height, int heightSize){
    int i=0, j=heightSize-1;
    int max=-1;//给max赋初值，方便第一次比较
    int h,w;
    while(ih,则仍需从h处进行比较，因为height[i]*w无法与h*w进行比较；若height[i]<=h，则无论如何h*w>height[i]*w，i继续向右移动                
            i++;
        }
        else
        {
            h=height[j--];//h取当前height[j]（较小值），同时j向做左移动
            while(ih,则仍需从h处进行比较，因为height[j]*w无法与h*w进行比较；若height[j]<=h，则无论如何h*w>height[j]*w，j继续向左移动
                j--;
        }
        max= max 
 这样就不用超时了！
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5659789.html