双指针算法：盛最多水的容器

题目介绍

11. 盛最多水的容器 - 力扣（LeetCode）

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

提示：

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

算法原理

暴力枚举

最直观的方法是枚举所有可能的两条线组合，计算面积并取最大值。但时间复杂度为 O(n²)，在数据量较大时会超时。

双指针优化

为了降低时间复杂度，可以使用双指针法。初始化左指针 left 指向数组头部，右指针 right 指向数组尾部。

容器的面积由较短的边决定（短板效应）。每次移动指针时，宽度必然减小。为了使面积可能增大，必须尝试增加高度。因此，我们总是移动高度较小的那一侧的指针：

1. 如果 height[left] < height[right]，则移动左指针 left++。
2. 如果 height[left] > height[right]，则移动右指针 right--。
3. 如果两者相等，同时移动两端。

这样可以在 O(n) 的时间内找到最大面积。

提交代码

public int maxArea(int[] height) {
    int left = ;
       height.length - ;
       ;
    
     (left < right) {
           Math.min(height[left], height[right]) * (right - left);
         (v > ret) {
            ret = v;
        }
         (height[left] < height[right]) {
            left++;
        }   (height[left] > height[right]) {
            right--;
        }  {
            left++;
            right--;
        }
    }
     ret;
}