盛最多水的容器

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

        Max_V = 0

        for i in range(len(height)):#左边界

                for j in range(i+1,len(height)):  #右边界

                   V = (j-i) * min(height[i],height[j])#计算宽度乘高度

                  Max_V=max(Max_V,V)#迭代

          return Max_V

法二（贪心算法）

让双指针左右边界，分别位于最左和最右，然后更新较矮者left++或者right--

在证明前，先统一几个前提定义，方便后续推导：

1. 设数组 height 长度为 n，左指针 l（初始 0），右指针 r（初始 n-1）；
2. 任意两个指针 (i,j)（i<j）构成的容器水量 V(i,j) = (j-i) * min(height[i], height[j])；
3. 最优解为 V_max = max{ V(i,j) | 0≤i<j<n }，对应最优指针对 (i*,j*)。

---

第一步：核心证明思路（反证法 + 排除法）

我们的目标是证明：双指针法在遍历过程中，一定会遇到最优指针对 (i*,j*)，且不会错过它。

证明的核心逻辑是：每次移动较矮指针时，我们只是排除了 “不可能成为最优解” 的无效容器，并没有排除最优解本身。

---

第二步：分情况推导（关键）

假设当前指针为 (l, r)（l<r），且 height[l] < height[r]（同理可证 height[l] > height[r] 的情况），此时我们选择移动左指针 l（较矮的那个）。

我们需要证明：所有以 l 为左指针、j 为右指针（l<j<r）的容器 V(l,j)，都不可能比 V(l,r) 更大，更不可能是最优解—— 也就是说，放弃 l，移动它是安全的，不会漏解。

推导过程：

1. 对于任意 j（l<j<r），容器 V(l,j) 的两个决定因素：

   • 宽度：j - l < r - l（因为 j<r），宽度变小；
   • 高度：min(height[l], height[j]) ≤ height[l]（因为 height[l] 是固定值，最小值不可能超过它）；而我们已知 height[l] = min(height[l], height[r])（因为 height[l] < height[r]）。

2. 综合来看：V(l,j) = (j-l) * min(height[l], height[j]) < (r-l) * height[l] = V(l,r)。

3. 结论：所有 V(l,j)（l<j<r）都 < V(l,r)，且 V(l,r) 本身又 < V(l*,r*)（最优解）。因此，这些 V(l,j) 都不可能是最优解，保留 l 没有任何意义，移动 l 是安全的，不会遗漏最优解。

---

第三步：为什么不会错过最优解 (i*,j*)？

双指针法的初始状态是 (0, n-1)（最宽容器），后续每次移动都在排除无效解，而最优解 (i*,j*) 一定会在指针收缩的过程中被遍历到：

1. 假设最优解是 (i*,j*)，在双指针遍历到 i* 或 j* 时，由于上述推导的规则，指针不会跳过 i* 或 j*，直到两个指针同时指向 i* 和 j*；
2. 当指针遍历到 (i*,j*) 时，会计算 V(i*,j*)，并更新为当前最大值；
3. 后续的指针移动只会排除比它更小的无效解，不会改变这个最大值。

---

第四步：特殊情况补充（height[l] = height[r]）

当 height[l] = height[r] 时，移动左指针或右指针均可，原因：

• 此时 V(l,r) = (r-l)*height[l]；
• 所有 V(l,j)（l<j<r）和 V(i,r)（l<i<r）都 < V(l,r)；
• 移动任意一个指针，都不会遗漏最优解，后续遍历仍会覆盖到可能的更优解（实际不存在，因为此时 V(l,r) 已经是当前最优）。

class Solution:

    def maxArea(self, height: List[int]) -> int:

        left = 0#左边界

        right = len(height)-1#右边界

        V_max = 0

        while(right>left):

            V = (right - left) * min(height[left],height[right])#计算体积

            V_max = max(V, V_max)#更新体积

            if height[left]<height[right]:#更新边界

                left+=1

            else:

                right-=1

        return V_max