盛水最多的容器
- .
- 习题链接
- 题目
- 题目解析
- 算法原理
- 我的答案
.
习题链接
盛水最多的容器
题目
题目解析
V=H*W
h为左右两边低的一边,w为左右两边之间的距离
算法原理
定义两个指针
left=0,right=n-1;
left从左往右对数组进行遍历,right从右往左进行遍历
遍历的过程中,每一次都需要记录当前容器的体积
关键:
因为V=H*W
,而w在遍历的过程中一直在减小
,对于较小的一边来说,遍历的过程中,会出现两种结果:
假如最小的是左边,固定左边,遍历右边,会出现以下两种情况:
- 假如遇到的值比之前的左边小,
会导致h减小
,从而使得v减小 - 假如遇到的值比之前左边的大,甚至比右边的都大,但是对容器的高度h没有影响,因此,还是会使得v减小
因此,分析可以得出,固定高度低的一方,遍历的结果都是没有意义的,因此,我们只需要将其跳过就行,当前情况下,我们就可以使用left++,来跳过这个数
期间每次都需要计算当前的容量,直到left与right相遇,找到所有v中的最大值,就是题目的结果
我的答案
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length-1;
int W = 0,H=0,V=0,max=0;
while(left<right){
W=right-left;
H=Math.min(height[left],height[right]);
V=H*W;
max=Math.max(max,V);
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return max;
}
}