问题描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
提示：
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
示例
示例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
解题思路
这里最简单的思路就是双重遍历数组，计算每两条边作为容器时的容量，然后找出最大值即可。但是这样的做法太复杂，可以进行优化。我们在双重遍历的时候，外面的循环从左往右遍历，里面的循环从右往左遍历，并且分别记录左右两边的最大值，如果从左往右遍历时，发现新的边小于最大值，说明该边组成的容器的容量不可能是最大的。代码如下：
class Solution {
public:
int maxArea(vector<int>& height) {
int maxVolume = 0;
int volume = 0;
int width = 0;
int maxLeft = 0;
int maxRight = 0;
for(int i = 0; i < height.size(); i++){
if(maxLeft < height[i]){
maxLeft = height[i];
}
else{
continue;
}
width = height.size() - i - 1;
maxRight = 0;
for(int j = height.size() - 1; j > i; j--){
if(maxRight < height[j]){
maxRight = height[j];
volume = (width--) * (height[i] < height[j] ? height[i] : height[j]);
if(maxVolume < volume){
maxVolume = volume;
}
}
else{
width--;
continue;
}
}
}
return maxVolume;
}
};
然而，上述代码还是太过复杂，时间复杂度仍然是 O(N^2) ，是否可以再进行简化呢？
答案是可以。实际上我们不需要使用双重循环，只需要使用双指针，遍历一次数组即可。我们令指针 i 指向数组的左边， j 指向数组的右边。计算此时 i 和 j 所在边作为容器时的容量，并比较 i 和 j 所指向边的长短。如果 height[i] < height[j] ，则将 i 向后移动； 如果 height[j] < height[i] ，则将 j 向前移动。
让我们分析一下这么做的原因。先看第一种情况，height[i] < height[j] ，计算此时的容积为 v1 = (j - i) * (height[i]) 。此时，如果继续保持 i 不变， j 向前移动，记作 j' ，那么无论 height[j'] 取值多少，得到的容积都不大于 v2 = (j' - i) * (height[i]) ，由于 j' < j ，因此 v1 > v2 成立。
另外一种情况也类似，当 height[j] < height[i] 时， 若 j 不变， i 移动， 得到的结果也不可能大于先前的结果。
因此，这个问题我们可以简化为只移动 i 和 j ，对 height 数组进行一次遍历。同时，为了减小遍历次数，我们也可能让 i 和 j 每次移动后，都保证新的边长度比原来的边长度更长，即 height[i'] > height[i] ， height[j'] > height[j] 。
class Solution {
public:
int maxArea(vector<int>& height) {
int maxVolume = 0;
int volume = 0;
int maxLeft = 0;
int maxRight = 0;
int i = 0;
int j = height.size() - 1;
while(i < j){
if(height[i] < height[j]){
volume = (j - i) * height[i];
maxLeft = height[i];
while(height[++i] < maxLeft);
}
else{
volume = (j - i) * height[j];
maxRight = height[j];
while(height[--j] < maxRight);
}
if(maxVolume < volume){
maxVolume = volume;
}
}
return maxVolume;
}
};