第一题：盛最多水的容器

1. 题目： 盛最多水的容器

代码语言：txt复制

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

说明：你不能倾斜容器。

2. 解答：暴力法

固定起点，遍历每一个可能的终点，计算最大面积。

圈复杂度：n^2

代码语言：txt复制

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxArea = 0

        for i, x in enumerate(height):
            k = 0
            area = 0
            for y in height[i   1::]:
                k  = 1
                area = max(area, k * min(x, y))
            maxArea = max(maxArea, area)
        
        return maxArea

执行超时，通过用例：49/60

image.png

3. 优化：双指针法

先找到最大宽度，即两个指针分别指向容器的开头和结尾；

然后找指针向中间移动，此时无论移动左边还是右边宽度都会减1，则要保留较高的点才能获得更大的面积（把高度低的点移出去），同时用当前宽度和高度更新最大面积

代码语言：txt复制

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 1
        right = len(height)
        maxArea = 0

        while right > left:
            if height[left - 1] < height[right - 1]:
                area = (right - left) * height[left - 1]
                left  = 1
            else:
                area = (right - left) * height[right - 1]
                right -= 1
            maxArea = max(maxArea, area)
        
        return maxArea

image.png

腾讯微信算法大赛 python

0 人点赞