首先记录一下题目的解法。使用双指针记录容器的边界,从边界最大的容器开始,i
位于最左侧,j
位于最右侧。每次向中间移动高度较小的那个指针,并使用一个变量res
记录容器最大的容积(即最终的答案)。
// C++
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1;
int res = 0;
while (i < j) {
int area = (j - i) * min(height[i], height[j]);
res = max(res, area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
};
// Java
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int res = 0;
while (i < j) {
int area = j - i;
if (height[i] < height[j]) {
area *= height[i];
res = Math.max(res, area);
i++;
} else {
area *= height[j];
res = Math.max(res, area);
j--;
}
}
return res;
}
}
官方的题解中解释了这种做法的正确性。我在这里记录一下我的直观想法。对于这种题目,最粗暴的想法自然是使用双重循环遍历每一种边界下标组合,记录最大的那个答案,显然对于较大的数据量来说,这种做法的时间复杂度为平方级,很容易超时。那么我们该如何进行剪枝,跳过一些情况的判断呢?将两个指针放在最远的两端开始向中间靠拢,\(S=(j-i) \times min(h_i, h_j)\),当指针向中间移动时,第一个乘数项一定变小,要想让整体的面积(容器的容积)变大,第二个乘数就只能变大,如果我们移动高度较大的那个指针(假设height[i] < height[j]
,我们移动j
),\(min(h_i,h_j)\)这一项仍然由高度较小(即i
和height[i]
)的那一项决定,也就是说移动高度较大的指针不会使这一项变大,当且仅当我们移动高度较小的那个指针时,才有可能使得此项变大。这也是为什么我们每次移动其中一个指针的原因。