力扣11，盛更多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

输入：height = [1,1]
输出：1

#include
#include

using namespace std;

class Solution
{
    public:

    int minNum(int num1,int num2)
    {
       return num1
        return height*width;
    }
//超出时间限制
    int maxArea(vector&height)
    {
        int maxAreaNum=0;
        int length=height.size();
        for(int i=0;i
            for(int j=i+1;j
                int temp=minNum(height[i],height[j]);
                int area=countArea(temp,j-i);

                if(maxAreaNum
                    maxAreaNum=area;
                }
            }
        }
        return maxAreaNum;

    }
};


int main()
{
    vectorheight={1,1};
    Solution sol;
    int maxAreaNum;
    maxAreaNum=sol.maxArea(height);
    cout< 
暴力解法，采用两个for循环，对所有产生的结果进行遍历，但是这种实现方法的时间复杂度比较高达到O(
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       n^2
      
     
    n2)的复杂度。但是这种方法同时面对较长的数组的时候，往往效果并不是特别好，因此在leetcode的判别中，爆出超出时间限制的错误。
 
方法二 贪心算法与双指针 
    int maxArea2(vector&height)
    {
        int maxAreaNum=0;
        int length=height.size();
        int i=0;
        int j=length-1;
        while(i
            //计算当前的值的大小
            int temp=minNum(height[i],height[j]);
            int area=countArea(temp,j-i);
            if(maxAreaNum
                maxAreaNum=area;
            }
            
            //双指针移动方法，小的先移动
            if(height[i]
                i++;
            }
            else{
                j--;
            }
            
        }
        return maxAreaNum;
    }
 
本题最好的解法就是使用贪心算法，因为最大的面积往往出现再，坐标较长和heightp[i]值较长的哪一个，因此可以采用头尾两个指针。每次迭代从较小的那个指针开始一种，直到两个指针碰头就好了。这种算法的时间复杂度为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)