leetcode 11.盛最多水的容器
第十一题:盛最多水的容器
1.暴力枚举:
会超时,但是做一些条件判断应该可以擦边过
public int maxArea(int[] height) {
int max_result = 0;
for (int i = 0;i<height.length-1;i++){
for (int j = i+1; j<height.length;j++){
int temp_result = Math.min(height[i],height[j]) * (j-i);
max_result = Math.max(temp_result,max_result);
}
}
return max_result;
}
2.双指针:
面积是长度较小值*距离,先将距离拉到最大,然后求出此时面积。在距离减小的情况下,只能试图调高长度增大面积,所以会将小的那个长度移动,试图变大,且左右指针不能重合。
- 时间复杂度:O(N),双指针总计最多遍历整个数组一次。
- 空间复杂度:O(1),只需要额外的常数级别的空间。
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int temp_result = 0;
int max_result = Math.min(height[height.length-1] ,height[0]) * (height.length-1);
while (left < right){
if (height[left] < height[right]){
left++;
}
else right--;
temp_result = Math.min(height[left] , height[right]) * (right - left);
max_result = Math.max(temp_result,max_result);
}
return max_result;
}
标签:11,right,int,max,height,result,最多水,leetcode,left
From: https://www.cnblogs.com/ldy20020324/p/17956054