一、题目描述
给你 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官方题解
1. 双指针
这道题归根结底就是求面积。两个元素下标之差为长，两元素之中小的那个为宽。在数组中找出这样两个元素，满足面积最大化。
采用双指针写法，创建两个指针left和right。分别从数组头部和尾部开始移动，对left和right指向的元素进行比较，如果left只想的元素小于right指向的元素，则left += 1,反之则right -= 1，意思就是谁小谁动。
三、代码实现
1. 双指针
class Solution:
def maxArea(self, height: List[int]) -> int:
res = 0
left = 0
right = len(height) - 1
while left < right:
if height[left] >= height[right]:
res = max(res, height[right] * (right - left))
right -= 1
else:
res = max(res, height[left] * (right - left))
left += 1
return res四、表现
| method | 运行时间 | 表现 | 内存消耗 | 表现 |
|---|---|---|---|---|
| 1. 双指针 | 76ms | 48.11% | 14.8MB | 26.71% |
