Python如何实现LeetCode第11题——最大容量容器问题？

本文共计607个文字，预计阅读时间需要3分钟。

Python描述LeetCode 11. 盛最多水的容器 — 大家常问（qì+guǎn+jí+）在【Python爱好者】公众号、GitHub、B站等平台分享一些技术博客，主要涵盖前端开发、Python后端开发、小程序开发等。

Python描述 LeetCode 11. 盛最多水的容器

  大家好，我是亓官劼（qí guān jié ），在公众号、GitHub、B站等平台分享一些技术博文，主要包括前端开发、python后端开发、小程序开发、数据结构与算法、docker、Linux常用运维、NLP等相关技术博文，时光荏苒，未来可期，加油~

  如果喜欢博主的文章可以关注博主的个人公众号(qí guān jié)，里面的文章更全更新更快。如果有需要找博主的话可以在公众号后台留言，我会尽快回复消息.

本文原创为（qí guān jié ），请大家支持原创，部分平台一直在恶意盗取博主的文章！！！ 全部文章请关注微信公众号。

题目

给定一个长度为 ​​n​​​ 的整数数组 ​​height​​​ 。有 ​​n​​​ 条垂线，第 ​​i​​​ 条线的两个端点是 ​​(i, 0)​​​ 和 ​​(i, height[i])​​ 。

找出其中的两条线，使得它们与 ​​x​​ 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

提示：

• ​​n == height.length​​
• ​​2 <= n <= 105​​
• ​​0 <= height[i] <= 104​​

解题思路

双指针。从两边向中间移动指针，不断更新最大盛水面积。每次移动时，优先移动柱子短的的一端，使其尽可能的高。

Python描述

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