题解 | #盛水最多的容器#
盛水最多的容器
https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47
方法一：暴力解法，双重循环取最大值
public int maxArea (int[] height) {
// write code here
int maxArea = 0;
int area = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i+1; j < height.length; j++) {
area = (j - i) * Math.min(height[i],height[j]);
maxArea = Math.max(maxArea,area);
}
}
return maxArea;
}
// write code here
int maxArea = 0;
int area = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i+1; j < height.length; j++) {
area = (j - i) * Math.min(height[i],height[j]);
maxArea = Math.max(maxArea,area);
}
}
return maxArea;
}
方法二：滑动窗口算法（贪心算法）：设置左右两个指针，选取高度小的那个为上限，计算当前左右柱子围起来的水量和max哪个大即可。
最开始两个下标放在首部和尾部，最短的那个往内收缩，选择最大的面积即可。
public int maxArea (int[] height) {
// write code here
int max = 0;
int area = 0 ;
int i = 0;
int j = height.length - 1;
while (i < j) {
int length = Math.min(height[i],height[j]);
area = (j - i ) * length;
max = Math.max(max , area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return max;
}
// write code here
int max = 0;
int area = 0 ;
int i = 0;
int j = height.length - 1;
while (i < j) {
int length = Math.min(height[i],height[j]);
area = (j - i ) * length;
max = Math.max(max , area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return max;
}
查看20道真题和解析
