【算法|双指针系列No.4】leetcode11. 盛最多水的容器

点解直接跳转到该题目

1️⃣题目描述

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

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

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

说明：你不能倾斜容器。

示例1：

示例2：

注意：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2️⃣算法分析

通过不断地调整较短的边界来寻找可能的最大容量。因为容器的容量受限于较短的边界，所以选择移动较短的边界可以增加容器的高度，有可能得到更大的容量。通过不断缩小指针之间的宽度，直到指针重合，即可得到最大容量。

容器容量：v = s * h，由于我们这里不断移动两个“指针”，所以 s 是不断变小的，那么问题来了，我们要移动哪个指针呢（是向右移动左指针的，还是向左移动右指针呢？），我们要知道无论我们移动哪一个指针容器的 s 都是减小的，此时如果要使得容器容量增大，我们需要移动指针指向的值较小的那个指针。举个例子（1，9），我们此时就需要向右移动左指针了，因为我们只有移动左指针才有可能使得容器的容器容量变大（即通过增加h的方式）。
即：

if(height[l] < height[r]) l++;
else r--; 

3️⃣代码编写

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0,r = height.size() - 1,ret = 0;
        while(l < r)
        {
            int v = (r - l) * min(height[l],height[r]);
            ret = max(v,ret);
            if(height[l] < height[r]) l++;
            else r--; 
        }
        return ret;
    }
};