11. 盛最多水的容器
1.思路
A.记录每一个left,right之间的所能构成的面积,求出其中的最大值
即Math.min(height[left],height[right])找出短的木板代表高,他们的宽为[right - left]
image.png
然后依次比较,两层for循环就能解决
B.是否有必要比较所有的结果?
肯定是没必要的,因为
image.png
如果构成的面积即没有原来的宽长也没有原来的高长,那么一定小于原来的面积
那么怎么去掉多余的面积呢?
1.找到所有可能比现在大的面积就行了
利用双指针,固定一端,寻找另一端,那么怎么变呢?
2.比较可能大的面积方向
设初始left =0,right = height.length-1
image.png
因为height[left] <height[right]
那么初始化的面积为 height[left]*(right - left)
image.png
1.left++(左边前进一格)
a.height[left++]>height[right]
area = height[right]*[right-left-1] 因为height[left] <height[right]
且height[left]*[right-left]那么这个面积有可能大于面积
b.height[left++]<=height[right]
area = height[left++]*[right-left-1] 因为height[left] <height[right]
且height[left]*[right-left]那么这个面积有可能大于面积
2.right--(右边前进一格)
a.height[left]>height[right--]
area = height[right--]*[right-left-1] 因为height[right--]<height[left] <height[right]
且height[left]*[right-left]那么这个面积有不可能大于原面积
b.height[left]<=height[right--]
area = height[left]*[right-left-1] 因为height[left] <height[right]
且height[left]*[right-left]那么这个面积也不可能大于原面积
总结:
左边的高度大于右边,那么右边移动,右边的高度大于左边,那么左边移动
2.代码
public int maxArea(int[] height) {
int max = 0;
int left = 0, right = height.length - 1;
while(left<right){
int area = (right - left +1 ) *Math.min(height[left],height[right]);
if(area>max){
max = area;
}
if(height[left]>height[right]){
right--;
}else{
left++;
}
}
return max;
}
