11.Container With Most Water

能够想到的最传统的方法：

class Solution {

public:

int maxArea(vector& height) {

int len=height.size();

int maxarea=0;

int area;

int heightmin;

for (int i=0;i

for(int j=i;j

heightmin=min(height[i],height[j]);

area=heightmin*(j-i);

maxarea=(maxarea>area)?maxarea:area;

}

}

return maxarea;

}

};

相当于将所有的Cn2种情况都遍历了一遍。

erro.JPG

样本特别大就没办法啦。会超时的。

那么！时间复杂度小很多的解法！
从两头找。较短的那一条边往中间移一个！
因为如果是长的那个移动，无论如何水的高度都不会高过短的那条边了，面积肯定不会增加的。只有改变短的才有希望！
天哪太机智了！！

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len=height.size();
        int maxarea=0;
        int area;
        int heightmin;
        int i=0;
        int j=len-1;
        while(j-i>0)
        {   
            if (height[i]<height[j])
            {area=height[i]*(j-i);
                i++;}
            else 
            {  area=height[j]*(j-i);
                j--;}
            maxarea=(maxarea>area)?maxarea:area;
        }
        return maxarea;
    }
};