一、 算法核心思想该算法的核心在于双指针Two Pointers与贪心策略。容器的容量由两个因素决定底部的宽度左右指针之间的距离 (right−left)。容器的高度左右两条垂线中的较低者 min(height[left],height[right])。水量的计算公式为Area(right−left)×min(height[left],height[right])指针移动逻辑算法初始时将left指向数组首端right指向数组尾端。此时容器的宽度达到最大。随后指针向内移动宽度必然减小。为了寻找可能更大的面积必须提升容器的高度。因此每次移动时哪侧的垂线较低就移动哪侧的指针如果 height[left]height[right]则left如果 height[left]≥height[right]则right--二、 代码逐行拆解与执行流程class Solution { public int maxArea(int[] height) { // 1. 初始化双指针分别指向数组的起始位置和结束位置 int left 0; int right height.length - 1; // 2. 初始化最大水面积变量 int ans 0; // 3. 当左右指针未相遇时执行循环 while (left right) { // 4. 计算当前指针位置构成的容器面积 int area (right - left) * Math.min(height[left], height[right]); // 5. 更新历史最大面积 ans Math.max(ans, area); // 6. 贪心策略移动高度较小的指针 if (height[left] height[right]) { left; // 左指针向右移动 } else { right--; // 右指针向左移动 } } // 7. 返回最终计算出的最大面积 return ans; } }三、 贪心策略的正确性证明为什么可以漏掉其余状态设左指针指向的基准高度为 xheight[left]右指针指向的基准高度为 yheight[right]。假设此时 xy即左边界较短。 若固定左边界 left将右边界 right 向内移动到 right−1新的宽度一定会减少。新的高度最大不会超过 x因为即便 height[right−1] 非常大容器高度依然受限于短板 x。因此在 left 不变的情况下排除内部所有的右边界状态其对应的面积都必然小于当前面积Areanew​≤(right−1−left)×x(right−left)×x这意味着以当前 left 为左边界的所有其他组合都不可能产生更大的面积。因此直接放弃 left 并执行left是完全正确的不会漏掉最优解。四、 复杂度分析1. 时间复杂度分析双指针left和right分别从数组的两端出发每一步循环都有且仅有一个指针向内移动一个单位。总步数两指针相遇时循环结束指针移动的总次数为 n−1 次。结论时间复杂度为 O(n)其中 n 为数组height的长度。2. 空间复杂度分析算法在运行过程中只创建了left、right、ans、area这四个整型变量。变动情况所分配的辅助空间不随输入数据规模 n 的增大而增大属于常数级额外空间。结论空间复杂度为 O(1)。