问题

给定一个长度为 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

解法

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        给定一个由若干个非负整数组成的数组 height，每个非负整数表示柱状条形的高度。
        计算按顺序选择任意两个柱状条形，使得它们之间的距离最小，且它们的底部在数组的两端。
        返回它们所能构成的最大矩形面积。

        :param height: List[int] 柱状条形的高度列表
        :return: int 最大矩形面积
        """
        l, r = 0, len(height) - 1  # 初始化左右指针
        ans = 0  # 初始化最大面积为0
        while l < r:  # 当左指针小于右指针时循环
            area = min(height[l], height[r]) * (r - l)  # 计算当前面积
            ans = max(ans, area)  # 更新最大面积
            if height[l] <= height[r]:  # 如果左边高度小于等于或小于右边高度
                l += 1  # 移动左指针
            else:  # 否则移动右指针
                r -= 1
        return ans  # 返回最大面积

实现步骤：

1. 初始化两个指针 l 和 r 分别指向列表的起始位置（索引0）和结束位置（索引 len(height) - 1）。
2. 初始化变量 ans 为0，用于存储遍历过程中找到的最大矩形面积。
3. 使用 while 循环，条件是 l 指针小于 r 指针，以此遍历列表。
4. 在循环中，计算当前左右指针之间的面积 area，公式为 min(height[l], height[r]) * (r - l)，其中 min(height[l], height[r]) 表示左右指针指向的高度中的较小值，(r - l) 表示左右指针之间的宽度。
5. 更新 ans 为 ans 和 area 中的较大值。
6. 比较左右指针指向的高度，将指向较小高度的指针向右移动一位（如果 height[l] <= height[r]），否则将右指针向左移动一位（else）。
7. 当 l 指针和 r 指针相遇时，循环结束。
8. 返回 ans 变量的值，即最大矩形面积。

算法复杂度

• 时间复杂度：O(N)，双指针总计最多遍历整个数组一次。

• 空间复杂度：O(1)，只需要额外的常数级别的空间。