法一:暴力解法(超时)
int maxArea(vector<int>& height) {
int max = 0;
for(int i = 0; i<height.size(); i++){
for(int j = i+1; j<height.size(); j++){
int minHeight = min(height[i], height[j]);
int capacity = (j-i) * minHeight;
if (capacity > max)
{
max = capacity;
}
}
}
return max;
}
法二:双指针
- 设置双指针index1和index2分别指向数组开始和结尾
- minHeight为双指针所指元素的较小值
- 容积capacity=(index2-index1)*minHeight
- 若index1所指元素较短,则index1++后,即移动短板,容积可能增大,可能减小或不变。
- 若index2所指元素较长,则index2--后,即移动长板,容积可能不变,可能减小。
- 因此只需移动短板,就可能获得较大容积。
int maxArea(vector<int> &height)
{
int index1 = 0, index2 = height.size() - 1;
int minHeight = 0;
int capacity = 0;
while (index1 != index2)
{
if (height[index1] > height[index2])
{
minHeight = height[index2];
if ((index2 - index1) * minHeight > capacity)
{
capacity = (index2 - index1) * minHeight;
}
index2--;
}
else
{
minHeight = height[index1];
if ((index2 - index1) * minHeight > capacity)
{
capacity = (index2 - index1) * minHeight;
}
index1++;
}
}
return capacity;
}
标签:11,容器,capacity,盛水,int,minHeight,height,index2,index1
From: https://www.cnblogs.com/morehair/p/17947417