好的，我们开始学习一道新的经典题目：「盛最多水的容器」。

这道题非常有趣，它融合了数组、双指针和贪心算法，是面试中的高频题。

1. 题目描述

题目链接： 11. Container With Most Water

题目描述：
给你一个长度为 n 的整数数组 height。数组中的每个元素 height[i] 代表垂直线的长度，这些垂直线在图中等距排列，每条线的两个端点分别是 (i, 0) 和 (i, height[i])。

请找出由这些垂直线构成的容器，能够容纳最多水的那一个，并返回其能够容纳的最大水量。

说明： 你不能倾斜容器。

示例 1：

输入：height = [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

2. 第一步：理解问题与核心概念

我们先来明确几个关键点：

1. 容器： 由任意两条垂直线作为容器的左右壁。
2. 容器的宽度： 两条垂直线在 x 轴上的距离，即 right_index - left_index。
3. 容器的高度： 由两条垂直线中较短的那条决定。因为水会从短的那边溢出。
4. 容器的面积（水量）： 面积 = 宽度 × 高度。
   • 公式：Area = min(height[left], height[right]) * (right - left)

我们的目标： 在所有可能的左右壁组合中，找到那个能使 Area 最大的组合。

3. 第二步：初步思路 - 暴力枚举

最直接的想法是尝试所有可能的组合。

• 使用两个循环，外层循环 i 从 0 到 n-1，作为左壁。
• 内层循环 j 从 i+1 到 n-1，作为右壁。
• 对于每一对 (i, j)，计算面积 min(height[i], height[j]) * (j - i)。
• 用一个变量 max_area 记录遇到的最大面积。

代码思路：

def maxArea(height):
    n = len(height)
    max_area = 0
    for i in range(n):
        for j in range(i + 1, n):
            h = min(height[i], height[j])
            w = j - i
            max_area = max(max_area, h * w)
    return max_area

复杂度分析：

• 时间复杂度： O(n²)，因为有两层循环。对于数组长度 n 很大时（例如 10⁵），这个算法会非常慢，在 LeetCode 上会超时。
• 空间复杂度： O(1)，只使用了常数级别的额外空间。

这个方法是正确的，但效率太低。我们需要一个更聪明的方法。

4. 第三步：优化思路 - 双指针法

为什么暴力法慢？因为它做了很多不必要的计算。我们能否避免检查所有组合？

核心洞察：
我们设置两个指针，left 指向数组开头（索引 0），right 指向数组末尾（索引 n-1）。这样，我们一开始就拥有了最大的宽度。

现在，关键问题来了：下一步我们应该如何移动指针？

• 容器的面积由较短的边和宽度共同决定。
• 如果我们移动指针，宽度一定会减小（因为 right - left 在变小）。
• 所以，为了有可能获得更大的面积，我们必须努力增加高度。

如何增加高度？
既然高度由短边决定，那么：

• 如果我们移动较长的那根指针，新的高度可能变大、变小或不变，但无论怎样，由于宽度减小了，面积的最大值只会不变或变小（因为高度上限仍然是原来的短边）。
• 但如果我们移动较短的那根指针，新的高度有可能变大，从而弥补宽度减小带来的损失，使得总面积有增大的可能！

贪心策略：

1. 初始化 left = 0, right = n-1, max_area = 0。
2. 循环，当 left < right 时：
   a. 计算当前面积 area = min(height[left], height[right]) * (right - left)。
   b. 更新 max_area = max(max_area, area)。
   c. 比较左右指针的高度：
   - 如果 height[left] < height[right]，则移动左指针 left++（舍弃掉当前这个较短的边，去寻找可能更高的边）。
   - 否则，移动右指针 right--。
3. 循环结束，返回 max_area。

为什么这样是正确的？
因为我们每次都是「舍弃」掉当前不可能再提供更大面积的那一边。我们总是保留着更高的边，并希望另一边能变得更高。这个过程确保了我们在 O(n) 的时间内扫描了所有可能成为最优解的情况。

5. 第四步：举例说明双指针法

让我们用示例 height = [1,8,6,2,5,4,8,3,7] 来走一遍流程。

1. 初始状态： left=0 (height=1), right=8 (height=7), width=8。

   • 高度 = min(1, 7) = 1
   • 面积 = 1 * 8 = 8
   • max_area = 8
   • 左边矮，移动左指针：left = 1

2. 状态 2： left=1 (8), right=8 (7), width=7。

   • 高度 = min(8, 7) = 7
   • 面积 = 7 * 7 = 49
   • max_area = 49 (更新！)
   • 右边矮，移动右指针：right = 7

3. 状态 3： left=1 (8), right=7 (3), width=6。

   • 高度 = min(8, 3) = 3
   • 面积 = 3 * 6 = 18
   • max_area 保持 49
   • 右边矮，移动右指针：right = 6

4. 状态 4： left=1 (8), right=6 (8), width=5。

   • 高度 = min(8, 8) = 8
   • 面积 = 8 * 5 = 40
   • max_area 保持 49
   • 两边一样高，可以移动任意一边（比如移动左指针）：left = 2

5. ... 继续这个过程，直到 left 和 right 相遇。

最终，我们得到最大面积 49，而无需检查所有 n² 种组合。

6. 第五步：编写最终代码

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # 计算当前面积
        width = right - left
        current_height = min(height[left], height[right])
        area = width * current_height
        
        # 更新最大面积
        if area > max_area:
            max_area = area
            
        # 移动指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area

复杂度分析：

• 时间复杂度： O(n)。两个指针总共遍历了整个数组一次。
• 空间复杂度： O(1)。只使用了几个额外的变量。

7. 总结

这道题的精髓在于：

1. 理解核心公式： 面积 = 最小高度 × 宽度。
2. 从暴力法出发： 先想出正确但低效的解法，这有助于理解问题。
3. 关键优化洞察： 利用双指针从两端向中间移动，每次移动较短的那一边，这是一种贪心策略。它之所以正确，是因为我们排除了许多不可能成为最优解的情况。
4. 双指针法的应用场景： 这种方法常用于有序数组或像本题这样可以通过特定策略移动指针的数组，能将时间复杂度从 O(n²) 降低到 O(n)。

希望这个循序渐进的讲解能帮助你彻底理解这道题！如果还有任何疑问，请随时提出。