题目描述

题目链接

https://leetcode.cn/problems/container-with-most-water/

思路

1. 双指针算法

我们先从题目中的示例开始，一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。

[1, 8, 6, 2, 5, 4, 8, 3, 7]
 ^                       ^

在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为。此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由：

决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动数字较小的那个指针。

所以，我们将左指针向右移动：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                    ^

此时可以容纳的水量为。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                 ^

此时可以容纳的水量为。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^              ^

此时可以容纳的水量为。两指针对应的数字相同，我们可任意移动一个，例如左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
       ^           ^

此时可以容纳的水量为。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小的，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：，，。在我们移动指针的过程中，计算到的最多可以容纳的数量为，即为最终的答案。

2. 正确性证明

为什么利用双指针的做法求解是正确的？

双指针代表了什么？
双指针代表的是可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。在这之后，我们每次将对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了。

为什么对应的数字较小的那个指针不可能再作为容器的边界了？
考虑第一步，假设当前左指针和右指针指向的数分别为和，不失一般性，我们假设。同时，两个指针之间的距离为。那么，它们组成的容器的容量为：

如果我们保持左指针位置不变，那么无论右指针在哪里，这个容器的容量都不会超过了。注意，这里右指针只能向左移动，因为我们考虑的是第一步，也就是指针还指向数组的左右边界。我们任意向左移动右指针，指向的数为，两个指针之间的距离为，那么显然有并且，因为：

• 如果，那么；
• 如果，那么。

因此有：

即无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，这个左指针对应的数不会作为容器的边界了，那么我们就可以丢弃这个位置，将左指针向右移动一个位置。这样一来，我们将问题的规模减小了，被我们丢弃的那个位置就相当于消失了。此时的左右指针，就指向了一个新的、规模减少了的问题的数组的左右边界，因此，我们可以继续像之前考虑第一步那样考虑这个问题：

• 求出当前双指针对应的容器的容量；
• 对应数字较小的那个指针以后不可能作为容器的边界了，将其丢弃，并移动对应的指针。

• 最后的答案就是我们每次以双指针为左右边界（也就是「数组」的左右边界）计算出的容量的最大值。

  代码实现

  public int maxArea(int[] height) {
    int res = 0;
    // 定义i、j为左右指针
    int i = 0, j = height.length - 1;
    while (i < j) {
        int left = height[i];
        int right = height[j];
        // 计算当前面积
        res = Math.max(res, (j - i) * Math.min(left, right));
        if (left <= right) {
            // 窗口左侧右移
            i++;
        } else {
            // 窗口右侧左移
            j--;
        }
    }
    return res;
  }
  

  复杂度分析

• 时间复杂度：，双指针总计最多遍历整个数组一次。

• 空间复杂度：，只需要额外的常数级别的空间。