letcode 11.Container With Most Water(最大容器)

给定n（$n\ge 2$n≥2）个非负整数$a_1,a_2,...,a_n$a1​,a2​,...,an​,其中每一个代表一个坐标点$(i,a_i)$(i,ai​)，绘制n条垂线，使得线的两个端点为$(i,a_i)$(i,ai​)和$(i,0)$(i,0)。找到两条线，使得这两条线和x轴所形成的容器能乘最多的水。如下图所示：

Given n non-negative integers $a_1,a_2,...,a_n$a1​,a2​,...,an​ , where each represents a point at coordinate $(i,a_i)$(i,ai​). n vertical lines are drawn such that the two endpoints of line i is at $(i,a_i)$(i,ai​) and $(i,0)$(i,0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

下图是输入为[1,8,6,2,5,4,8,3,7]所形成的图形

样例：

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

如果枚举所有边，那就有$C_n^2$Cn2​中可能，也就是时间复杂度为$O(n^2)$O(n2)，但是使用贪心法就可以使得时间复杂度变为$O(n)$O(n)。

因为：面积=底边的长度*（两边中较低的一条的长度）

要使面积尽可能大，就要使乘法的两个因子尽可能大，所以我们从底边最大处开始，接下来底边只可能比原来的小，想要找到面积更大的，就要使“两边中较低的长度”比原来大。所以要将短的那条边换掉。然后重复该过程。直到左右指针相撞。

因为left和right都在“向中间靠拢”，所以循环次数为n次，时间复杂度为$O(n)$O(n)。

完整代码：

class Solution
{
public:
    int maxArea(vector<int>& height)
    {
        int a=0;
        int ans=0;
        int left=0,right=height.size()-1;
        while(left<right)
        {
            a=(right-left)*(height[left]<height[right]?height[left++]:height[right--]);
            ans = ans > a? ans : a;
        }
        return ans;
    }
};