11. 盛最多水的容器
1.思路
A.記錄每一個left,right之間的所能構(gòu)成的面積,求出其中的最大值
即Math.min(height[left],height[right])找出短的木板代表高,他們的寬為[right - left]
image.png
然后依次比較,兩層for循環(huán)就能解決
B.是否有必要比較所有的結(jié)果?
肯定是沒必要的,因為
image.png
如果構(gòu)成的面積即沒有原來的寬長也沒有原來的高長,那么一定小于原來的面積
那么怎么去掉多余的面積呢?
1.找到所有可能比現(xiàn)在大的面積就行了
利用雙指針,固定一端,尋找另一端,那么怎么變呢?
2.比較可能大的面積方向
設(shè)初始left =0,right = height.length-1
image.png
因為height[left] <height[right]
那么初始化的面積為 height[left]*(right - left)
image.png
1.left++(左邊前進(jìn)一格)
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--(右邊前進(jìn)一格)
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]那么這個面積也不可能大于原面積
總結(jié):
左邊的高度大于右邊,那么右邊移動,右邊的高度大于左邊,那么左邊移動
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;
}
