[python 刷题] 11 Container With Most Water-Toy模板网

这篇具有很好参考价值的文章主要介绍了[python 刷题] 11 Container With Most Water。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

[python 刷题] 11 Container With Most Water

题目：

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

这道题也是一个比较经典的双指针+贪心，求的事总面积，题目中已经提出容器无法被倾倒 🫗，在不考虑三角的情况下，面积的构成就是长（x 轴） x 宽（y 轴）的组合，

以案例 1 而言：[1,8,6,2,5,4,8,3,7]，分析如下：

当左右指针指向最两边时，面积是这样的：

[python 刷题] 11 Container With Most Water,# leetcode,python,开发语言

此时面积为 $\times 8$

可以看到，容器的面积是收到长和高的限制，而高的选取则为 $min (l e f t, r i g h t)$ ，也就是说，高都不变，指针之间的距离越小，面积自然就越小。

这个情况下，最合理的做法就是移动较低一边的指针，这样长度虽然减少了，但是高度增加的话，面积还是有可能会增加：

[python 刷题] 11 Container With Most Water,# leetcode,python,开发语言

此时的面积为 $\times 7$

接着重复这样的操作：

[python 刷题] 11 Container With Most Water,# leetcode,python,开发语言

一直到完成遍历即可

代码如下：

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

        while l < r:
            res = max(res, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return res