盛最多水的容器

给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量。说明：你不能倾斜容器。

示例 1：

• 输入：height = [1,8,6,2,5,4,8,3,7]
• 输出：49

示例 2：

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

提示：

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

解题思路：

1. 两条线之间能装多少水？由较矮一侧的高度和**两线间距（宽度）**的乘积决定。

2. 暴力枚举所有 (i, j) 对是 O(n²)，n=10⁵ 时约 10¹⁰ 次操作，超时。

3. 能不能跳过某些组合？对固定的 i=0，暴力是 j 从 1 扫到 n-1，最后才检查 (0, n-1)。把顺序反过来：先检查 j=n-1（最大宽度），再往左走。这样一检查完 (0, n-1)，就能立刻判断 i=0 这一行还需不需要继续：若 height[0] < height[n-1]，则 i=0 配所有 j'<n-1 的组合，宽度更小、高度上限仍被 height[0] 限制，结果只会更差，整行跳过，直接移到 i=1。

4. 因此：每次移动较矮的那侧，才有可能遇到更高的线来提升容积；移动较高的那侧只会让结果更差。

5. 终止条件：left < right，两指针相遇时停止——同一条线不能和自己构成容器。

C++

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int res = min(height[left], height[right]) * (right - left);
    while (left < right) {
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
        res = max(res, min(height[left], height[right]) * (right - left));
    }
    return res;
}

Python

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

Java

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int res = Math.min(height[left], height[right]) * (right - left);
    while (left < right) {
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
        res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
    }
    return res;
}

Go

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    res := min(height[left], height[right]) * (right - left)
    for left < right {
        if height[left] <= height[right] {
            left++
        } else {
            right--
        }
        res = max(res, min(height[left], height[right]) * (right - left))
    }
    return res
}

时间复杂度 O(n)，空间复杂度 O(1)。