1.题目链接
11. 盛最多水的容器 - 力扣（LeetCode）
https://leetcode.cn/problems/container-with-most-water/
2.题目描述
给定⼀个⻓度为 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 。
3.算法思路
该算法用于求解“盛最多水的容器”问题，采用双指针法高效寻找最大容量。其核心思想是通过逐步缩小指针间距，结合高度调整策略，确保不漏掉可能的更优解。具体步骤如下：
1. 双指针初始化
左指针
left初始指向数组起始位置（索引 0）。右指针
right初始指向数组末尾（索引n-1，n为数组长度）。
2. 容量计算与指针移动
计算当前容量：
- 容器的容积由较短的边决定
- 将
v与历史最大值ret比较，更新ret。
指针移动策略：
若
height[left] > height[right]：右指针左移（right--）。否则：左指针右移（
left++）。
关键逻辑：
- 移动较短的边，以尝试找到更高的边，从而可能获得更大容积。
3. 终止条件
当
left >= right时，双指针相遇，结束循环。最终返回记录的最大容积
ret。
算法正确性证明
贪心策略的有效性：
每次移动较短的边，可以确保不会错过可能的更优解。假设当前左指针高度较小，若固定左指针，右指针左移的所有情况中，容器的宽度减少且高度受限于左指针，容积必然更小。因此，必须移动左指针以寻找更高的边。覆盖所有可能解：
双指针从两端向中间移动，每次操作排除了一部分不可能成为最优解的情况。由于每次移动都基于当前状态的局部最优选择，最终能够覆盖所有潜在的最大容积情况。
示例分析
输入：
height = [1,8,6,2,5,4,8,3,7]初始状态：
left=0（高度1），right=8（高度7），容积为 1×8=81×8=8。移动较短边：左指针右移。
后续步骤：
left=1（高度8），right=8（高度7），容积 7×7=497×7=49。右指针左移，依次比较，最终得到最大容积 49。
复杂度分析
时间复杂度：O(n)，仅需一次遍历数组。
空间复杂度：O(1)，仅使用常量额外空间。
关键点总结
双指针高效缩小搜索范围：通过比较高度动态调整指针，避免暴力枚举所有组合。
数学优化：移动较短边的策略基于容积受限于较短边的特性，确保算法正确性。
一次遍历解决问题：时间复杂度优于暴力法的 O(n²)，适用于大规模数据。
4.代码实现
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0, right = height.size() - 1, ret = 0;
while(left < right)
{
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
if(height[left] > height[right]) right--;
else left++;
}
return ret;
}
};