【力扣】盛最多水的容器，双指针法

盛最多水的容器原题地址

方法一：双指针

如果使用暴力枚举，时间复杂度为  ，效率太低，会超时。

考虑使用双指针，利用单调性求解。用 left 和 right 作为数组 height 的下标，分别初始化为 0 和 size-1 。考虑在区间 [left,right] 的范围内，理论上会有  种配对可能，但其中有一些情况不需要再考虑。其中 容量 = 高度 * 宽度，即 area=min(height[left],height[right])*(right-left) 。

不妨设 height[left]<height[right] ，区间下标的所有可能取值为：

left left+1 left+2 ... right-2 right-1 right

那么 left 如果与 [left+1,right-1] 的值（记为 m ）配对，其 area 值一定比 left 与 right 配对小，为什么呢？这是因为宽度减小了，高度减小或不变（见下面的 2 种情况）。

1. 若 height[m]>height[left] ，那么高度不变，仍然为 height[left] 。
2. 若 height[m]<height[left] ，那么高度减小为 height[m] 。

所以我们不需要考虑 left 与除了 right 之外的其余值配对，让 left 指针右移为 left+1 ，在 [left+1,right] 的范围内寻找新的配对。

同理，若 height[left]>height[right] ，则不需要考虑 right 和 [left+1,right-1] 的值配对，此时应该让 right 指针左移为 right-1 ，在 [left,right-1] 的范围内寻找新的配对。

若 height[left]=height[right] ，可归为前面任意一类。

这样，每次都可以缩减配对的范围，直到 left 和 right 相遇为止，其时间复杂度为 O(N) 。

// 方法一：双指针
class Solution
{
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        while (left < right)
        {
            // 计算容量
            int area = min(height[left], height[right]) * (right - left);
            ans = max(ans, area);

            // 高度小的那边不可能作为边界
            // 这是因为如果高度小的那边和其他边匹配，
            // 宽度会减小，高度不会增加，所以容量会减小
            if (height[left] < height[right])
            {
                ++left;
            }
            else
            {
                --right;
            }
        }

        return ans;
    }
};