🔗 盛最多水的容器

题目来源：11. 盛最多水的容器 – 力扣（LeetCode）

---

📌 题目描述

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

---

✅ 示例解析

示例 1：

• 输入：height = [1,8,6,2,5,4,8,3,7]
• 输出：49
• 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。对应的两条线为索引 1（高度 8）和索引 8（高度 7），宽度为 7，高度为 min(8,7)=7，面积为 7×7=49。

示例 2：

• 输入：height = [1,1]
• 输出：1
• 解释：两条线高度均为 1，宽度为 1，最大面积为 1×1=1。

---

⚠️ 提示

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

---

💡 解法：双指针法（左右夹逼）—— O(n) 时间，O(1) 空间

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, (right - left) * minHeight);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  双指针从两端向中间移动，最多遍历数组一次，每个元素访问一次，因此时间复杂度为线性。
• 空间复杂度：O(1)
  只使用了常数个额外变量（left, right, maxArea, minHeight），无需额外空间。

---

🧩 解题思路

1. 核心观察：
   容器的面积由两个因素决定：
   • 宽度：两指针之间的距离 right - left
   • 高度：由较短的那条边决定 min(height[left], height[right])
2. 贪心策略 + 双指针：
   • 初始时，left = 0，right = n - 1，此时宽度最大。
   • 每次计算当前面积，并更新最大值。
   • 然后移动较短边对应的指针。
     • 因为如果移动较长边，宽度减小，而高度仍受限于较短边，面积不可能变大。
     • 只有移动较短边，才有可能找到更高的边，从而获得更大的面积。
3. 为什么不会错过最优解？
   • 每次移动较短边，是在“牺牲宽度”的前提下，保留更高的边，为后续可能的更大面积创造机会。
   • 所有组合都会被隐式比较，但由于贪心剪枝，避免了暴力枚举。
4. 终止条件：
   当 left >= right 时停止，所有可能的组合已被考虑。