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

盛最多水的容器原题地址

方法一：双指针

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

考虑使用双指针，利用单调性求解。用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指针左移为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;
    }
};