leetcode---腾讯 盛最多水的容器

原题：
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

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

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49
在真实的面试中遇到过这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：
逐个比较，计算两两组合形成的容器的容积，记录其中最大的那个并返回
代码：

def maxArea(self, height: list) -> int: i = len(height) s = 0 for j in range(0,i): for h in range(j+1,i): g = (h-j)*min(height[j],height[h]) if g>=s: s=g return s c=[1,8,6,2,5,4,8,3,7] self=[] print(maxArea(self,c))

效果：

上面这种方法比较简单，复杂度为O（n^2),下面对其进行该进

由于容器的短板效应，较短的高度决定了容器的最大容量，因此我们从头、尾开始，逐一遍历，计算Left、right之间容器的容积；之后将高度较小的那个向另一端移动，直至两者重合，记录其中的最大值

代码：

def maxArea(self, height: list) -> int: i = len(height) left = 0 right = i - 1 s = 0 while (left<right): g = (right-left)*min(height[left],height[right]) if s<g: s=g if height[left]<height[right]: left = left+1 else: right = right-1 return s c=[1,8,6,2,5,4,8,3,7] self=[] print(maxArea(self,c))

这个算法的时间复杂度为O（n)
效果：