11. 盛最多水的容器

11. 盛最多水的容器

• n == height.length

• 2 <= n <= 105

• 0 <= height[i] <= 104

解题思路

算法流程

1. 初始化：

• 设置左指针 i 指向数组开头（i = 0）

• 设置右指针 j 指向数组末尾（j = n-1）

• 初始化结果变量 res = 0

1. 双指针移动策略：

• 计算当前面积：width = j - i（两线距离），height = min(height[i], height[j])（较短的线）

• 更新最大面积：res = max(res, width * height)

• 移动较短的那条线对应的指针：
• 如果 height[i] < height[j]，移动左指针 i++
• 否则移动右指针 j--

为什么这样做是对的？

1. 面积由两个因素决定：两条垂线的距离（宽度）和较短的垂线高度（高度）。

2. 初始时，两指针距离最远，宽度最大。

3. 我们总是移动较短的那条垂线对应的指针，因为：

• 如果移动较长的线，宽度减小，而高度不可能超过较短的线

• 移动较短的线，虽然宽度减小，但可能找到更高的线，从而得到更大的面积

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。指针移动n次即可完成遍历。

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