11、盛水最多的容器

如题

这道题用暴力破解的方法不难，但是在时间复杂度太高，容易出现超时情况。
这里我参考官方给出的思路，用Python写了一套。

双指针法

这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxareamaxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxareamaxarea，并将指向较短线段的指针向较长线段那端移动一步。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, max_area = 0, len(height)-1, 0
        while(i<j):
            max_area = max(min(height[i], height[j])*(j-i), max_area)
            if height[i]>=height[j]: j-=1
            else: i+=1
        return max_area

算法的核心思想是两头扫描，双指针。

复杂度分析

• 时间复杂度： o(n)：一次扫描
• 空间复杂度： o(1)：使用恒定的空间