11. 盛最多水的容器：在贪心算法框架下使用双指针.md

题目简述：

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

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

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

**说明：**你不能倾斜容器。

题目链接：11. 盛最多水的容器

算法思路

首先令两个指针 $\mathrm{left}$、$\mathrm{right}$ 分别表示某个理想容器的左右边界，然后初始化 $\mathrm{left}=0$、$\mathrm{right}=n-1$，接着我们每次让 $\mathrm{left}$ 和 $\mathrm{right}$ 中高度较低者向中间移动，并在每次移动后滚动更新并存储已知的容器最大容积，直到两指针相遇，结束算法。显然，两个指针一共移动 $n-1$ 次，因此算法的时间复杂度为 $O(n)$。

代码实现

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxVolume = (height.length - 1) * Math.min(height[0], height[height.length - 1]);

        while (left < right) {
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
            maxVolume = Math.max(maxVolume, (right - left) * Math.min(height[left], height[right]));
        }

        return maxVolume;
    }
}