题目描述

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

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

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

说明：你不能倾斜容器。

示例 1：

plaintext

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

plaintext

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

---

解题思路：双指针法

核心思路

这道题最高效的解法是双指针法，时间复杂度 O(n)，空间复杂度 O(1)，完美适配题目数据范围。

1. 指针初始化：左指针 left 指向数组起始位置（最左边），右指针 right 指向数组末尾（最右边）。
2. 面积计算：容器的容积 = 两指针间距（宽度） × 两指针指向的较小高度（高度），公式：min(height[left], height[right]) * (right - left)。
3. 指针移动规则：
   • 每次移动高度较小的一侧指针：因为容器的高度由短板决定，移动高侧指针无法增加容积，只有移动矮侧指针，才有可能找到更高的短板，从而增大容积。
4. 循环更新最大值：每次计算当前面积，与历史最大面积比较，保留最大值，直到两指针相遇。

为什么双指针法正确？

• 初始时两指针间距最大，是宽度最大的情况。
• 每次舍弃较短的边，保留较长的边，不会错过最优解，因为保留长边才有机会获得更大的容积。

---

Java 代码实现

java

运行

class Solution {
    public int maxArea(int[] height) {
        // 记录最大容积
        int maxarea = 0;
        // 左指针指向数组起始位置
        int left = 0;
        // 右指针指向数组末尾
        int right = height.length - 1;
        
        // 双指针未相遇时循环
        while (left < right) {
            // 计算当前容积，宽度=right-left，高度=左右指针较小值
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            // 更新最大容积
            maxarea = Math.max(maxarea, currentArea);
            
            // 移动较小高度的指针，寻找更大容积
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxarea;
    }
}

---

代码详解

1. 变量定义：

   • maxarea：存储遍历过程中找到的最大容积，初始值为 0。
   • left：左指针，初始为 0（数组第一个元素）。
   • right：右指针，初始为 height.length - 1（数组最后一个元素）。

2. 循环逻辑：

   • 循环条件 left < right：保证两指针不重叠，至少有两条线才能构成容器。
   • 每次计算当前指针围成的容积，用 Math.max 更新最大容积。
   • 比较左右指针的高度：左高度小就右移左指针，右高度小就左移右指针。

3. 返回结果：循环结束后，maxarea 即为最大容积。

---

复杂度分析

• 时间复杂度：O(n)，只需要遍历一次数组，双指针总共移动 n 次。
• 空间复杂度：O(1)，仅使用了常数个额外变量，没有开辟新的数组空间。

---

测试用例

用例 1

输入：[1,8,6,2,5,4,8,3,7]输出：49

用例 2

输入：[1,1]输出：1

用例 3

输入：[4,3,2,1,4]输出：16

---

总结

这道题是双指针法的经典应用，核心在于理解「容积由短板决定」，通过移动短板指针贪心寻找最优解，相比暴力枚举（O(n2)）效率大幅提升，是面试高频考点。