力扣11，盛更多水的容器

力扣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<num2?num1:num2;
    }

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

                if(maxAreaNum<area)
                {
                    maxAreaNum=area;
                }
            }
        }
        return maxAreaNum;

    }
};


int main()
{
    vector<int>height={1,1};
    Solution sol;
    int maxAreaNum;
    maxAreaNum=sol.maxArea(height);
    cout<<maxAreaNum<<endl;
}

暴力解法，采用两个for循环，对所有产生的结果进行遍历，但是这种实现方法的时间复杂度比较高达到O( n 2 n^2 n2)的复杂度。但是这种方法同时面对较长的数组的时候，往往效果并不是特别好，因此在leetcode的判别中，爆出超出时间限制的错误。

方法二 贪心算法与双指针

    int maxArea2(vector<int>&height)
    {
        int maxAreaNum=0;
        int length=height.size();
        int i=0;
        int j=length-1;
        while(i<j)
        {
            //计算当前的值的大小
            int temp=minNum(height[i],height[j]);
            int area=countArea(temp,j-i);
            if(maxAreaNum<area)
            {
                maxAreaNum=area;
            }
            
            //双指针移动方法，小的先移动
            if(height[i]<height[j])
            {
                i++;
            }
            else{
                j--;
            }
            
        }
        return maxAreaNum;
    }

本题最好的解法就是使用贪心算法，因为最大的面积往往出现再，坐标较长和heightp[i]值较长的哪一个，因此可以采用头尾两个指针。每次迭代从较小的那个指针开始一种，直到两个指针碰头就好了。这种算法的时间复杂度为 O ( n ) O(n) O(n)