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

原题给定 n 个非负整数 a1a2…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(j1,i): g (h-j)*min(height[j],height[h]) if gs: sg return s c[1,8,6,2,5,4,8,3,7] self[] print(maxArea(self,c))效果上面这种方法比较简单复杂度为On^2),下面对其进行该进由于容器的短板效应较短的高度决定了容器的最大容量因此我们从头、尾开始逐一遍历计算Left、right之间容器的容积之后将高度较小的那个向另一端移动直至两者重合记录其中的最大值代码def maxArea(self, height: list) - int: i len(height) left 0 right i - 1 s 0 while (leftright): g (right-left)*min(height[left],height[right]) if sg: sg if height[left]height[right]: left left1 else: right right-1 return s c[1,8,6,2,5,4,8,3,7] self[] print(maxArea(self,c))这个算法的时间复杂度为On)效果