方法

采用左右双指针夹逼的方式,从数组两端向中间遍历,逐步缩小范围,同时记录遍历过程中的最大面积,步骤如下:

  1. 初始化指针和最大面积:左指针left指向数组起始位置(0),右指针right指向数组末尾位置(n-1),最大面积maxArea初始值为 0;
  2. 双指针夹逼遍历:当left < right时,循环执行以下操作:
    • 计算当前容器的盛水量:用公式(right - left) × Math.min(height[left], height[right])
    • 更新最大面积:如果当前盛水量大于maxArea,则将maxArea替换为当前值;
    • 移动较矮的指针(核心技巧):
      • height[left] < height[right]左指针右移(因为矮边在左,此时移动高边(右)只会让宽度变小,盛水量不可能增加;只有移动矮边,才有可能找到更高的边,让盛水量变大);
      • 反之,右指针左移(同理,矮边在右,移动右指针才有可能提升高度);
  3. 返回结果:当左右指针相遇(left >= right)时,循环结束,此时maxArea就是容器能容纳的最大水量。

通俗理解核心技巧

矮边决定水量,移动矮边才有机会变大”,高边留在原地即可,避免无效的遍历,让整个过程只需要一次数组扫描。

示例验证(输入 [1,8,6,2,5,4,8,3,7])

  1. 初始:left=0(高度 1)、right=8(高度 7),面积 = 8×1=8,maxArea=8 → 左矮,左指针右移至 1;
  2. left=1(8)、right=8(7),面积 = 7×7=49,maxArea=49 → 右矮,右指针左移至 7;
  3. 后续持续移动较矮的指针,所有计算出的面积都小于 49,最终 maxArea=49,与示例输出一致。

代码实现

class Solution {
    public int maxArea(int[] height) {
        int left = 0; // 左指针
        int right = height.length - 1; // 右指针
        int maxArea = 0; // 最大盛水量
        while (left < right) {
            // 计算当前面积
            int curWidth = right - left;
            int curHeight = Math.min(height[left], height[right]);
            int curArea = curWidth * curHeight;
            // 更新最大面积
            if (curArea > maxArea) {
                maxArea = curArea;
            }
            // 移动较矮的指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

 

总结

  1. 盛水量核心公式:面积 = 左右指针间距 × 左右高度的较小值
  2. 最优解法为双指针夹逼法,从两端向中间遍历,移动较矮的指针是核心;
  3. 时间复杂度 O (n)、空间复杂度 O (1),适配题目大数据量要求。
  4. 希望能帮助到你,谢谢!

 

更多推荐