给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
解法一：暴力破解（超时）
枚举出能构成的所有容器，找出其中容积最大的值！
容器容积的计算方式：
设两指针 left 和 right，分别指向水槽板的最左端以及最右端，此时容器的宽度为 right - left。由于容器的高度由两板中的短板决定，因此可得容积公式 ：v = (right - left) * min( height[left], height[right])
class Solution {
public:
int maxArea(vector<int>& height) {
int maxret = -1;
for(int left = 0; left < height.size() - 1; ++left)
{
for(int right = height.size() - 1; right > left; --right)
{
maxret = max(maxret, (right - left)*min(height[left], height[right]));
}
}
return maxret;
}
};🎏 解法二：双指针
设两个指针 left 和 right，分别指向容器的左右两个端点，此时容器的容积为：v = (right - left) * min( height[left], height[right])。
为了避开枚举，我们必须找规律，就拿题目给的示例一来说：[1, 8, 6, 2, 5, 4, 8, 3, 7]，我们单独拿出其中的一个小区间 [6, 2, 5, 4] 来研究一下！
假设一开始 left 指向 6，而 right 指向 4，此时容积就是 宽度*短板高度，就是 3 * 4 = 12。
此时我们定住 right 不变，让 left 指向 2 还是 5 都行，可以看到，宽度变小了！也就是说容积肯定会收到影响；此时如果 left 指向 2，那么短板高度变成了 2，容积肯定就比之前小了！然后再看看 left 指向 5 的话，此时短板高度还是 4，但是因为宽度变小了，所以容积还是变小了！
找到规律了没有，一旦我们 left 往右走或者 right 往左走，宽度都会变小，此时容积取决于短板高度是否增大，如果短板高度比之前小了，那么容积就肯定变小了，就不需要考虑了！所以我们可以总结出算法步骤如下：
- 用
left和right指向容器的两端，然后都向里走，用一个变量maxret记录下途中算出来的最大容积。 - 接着判断
left和right哪个高度小，直接将高度小的排除。因为一旦高度小了，边界一收缩，那么容积就变小了，所以我们只需要留left和right两者中高度高的那个即可。 - 如果两个板的高度相等的话则规定排除
left。 - 循环上述步骤直到两个指针相遇！
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxret = -1;
while(left < right)
{
// 容积 = 短板高度 * 宽度
if(height[left] <= height[right])
{
maxret = max(maxret, height[left]*(right - left));
left++;
}
else
{
maxret = max(maxret, height[right]*(right - left));
right--;
}
}
return maxret;
}
};