leetcode.11 --- 盛最多水的容器

盛最多水的容器

暴力解法:

2层for循环，时间复杂度n方，本题会直接超时

代码如下：

class Solution {
    
public:
    int maxArea(vector<int>& height) {
      
        int res = 0;
        for(int i=0;i<height.size();i++)
        {
    
            for(int j=i+1;j<height.size();j++)
            {
    
                res = max(res,min(height[j],height[i])*(j-i));
            }
        }

        return res;
    }
};

解法二:
双指针解法，直接看题解，每次短的向前一步

代码如下:

class Solution {
    
public:
    int maxArea(vector<int>& height) {
    
        int i = 0,j = height.size() - 1,res = 0;
        while(i < j)
        {
    
            res = max(res,min(height[i],height[j]) * (j - i));
            if(height[i] < height[j]) i++;
            else j--;
        }
  
        return res;
    }
};

时间复杂度:O(n)

为什么双指针可以解决，可以看题解给出的证明即可。