难度: Medium
给定一个长度为 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.length2 <= n <= 1050 <= height[i] <= 104运行时间: 68 ms
内存: 16.2 MB
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
res = 0
while i < j:
if height[i] < height[j]:
res = max(res, height[i] * (j-i))
i += 1
else:
res = max(res, height[j] * (j-i))
j -= 1
return res
这个题解使用双指针的思路。初始时左指针 i 指向数组的最左端，右指针 j 指向数组的最右端。在左右指针相遇之前，每次计算以当前左右指针为边界形成的区域的面积，并更新最大面积 res。然后将 height[i] 和 height[j] 中较小的一个对应的指针向内移动一步。这样能保证，对于每个状态，左右指针只会向内移动，直到两个指针相遇，过程中会找到能够容纳最多水的两条线。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0 # 左指针，初始指向数组最左端
j = len(height) - 1 # 右指针，初始指向数组最右端
res = 0 # 存储最大面积
while i < j: # 当左右指针未相遇时
if height[i] < height[j]:
# 如果左指针高度小于右指针高度
# 计算当前左右指针形成的面积，并更新最大面积
res = max(res, height[i] * (j-i))
i += 1 # 左指针向右移动
else:
# 如果右指针高度小于等于左指针高度
# 计算当前左右指针形成的面积，并更新最大面积
res = max(res, height[j] * (j-i))
j -= 1 # 右指针向左移动
return res # 返回最大面积
在计算两个垂直线与 x 轴形成的容器的面积时，水的高度由两边较矮的线决定，因为水会从短的一边溢出。因此，使用 `min(height[i], height[j])` 确保不超过任一边的高度。直接使用 `height[i] * (j-i)` 或 `height[j] * (j-i)` 忽视了短边的限制，可能会估算出不实际的更大面积。
双指针方法确实能够找到最大水容纳量的最优解。这个方法的核心是通过比较两指针对应的高度来移动指针，从而逐步排除掉不可能产生最大面积的选项。该方法保证了每次移动都是在尝试寻找一个可能更大的面积，从而涵盖了所有可能的最大面积组合。
选择移动 `height[i]` 和 `height[j]` 中较小的一个对应的指针是为了增加找到更大面积的机会。若移动较高的指针，新形成的容器的高度依然受限于较低的旧边界，且宽度减小，这减少了可能的最大面积。而移动较低的指针有可能找到一个更高的边界，从而有可能增加面积。
是的，这个方法仍然有效。双指针法不受具体高度值的影响，而是通过比较两端的高度来决定移动哪个指针。即便数组中存在多个相同的最大高度，双指针法通过逐步移动指针，仍可以评估所有可能的容器，找到可以储存最多水的情况。
这个算法的空间复杂度是 O(1)。双指针方法只需要常数级的额外空间来存储指针和当前最大面积，它不需要额外的数据结构来存储中间结果或者数组副本。因此，它的空间需求不随输入数据的大小而变化。