给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解题思路
1.普通版
- 双指针
- 面积由最短的决定
class Solution {
public int maxArea(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int ans = 0;
while(left < right) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
if(height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
}
执行用时分布
5ms
击败12.01%使用 Java 的用户
消耗内存分布
56.61MB
击败10.37%使用 Java 的用户
2.优化版
不需要计算的就不要计算
class Solution {
public int maxArea(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int ans = 0;
int count = 0;
while(left < right) {
if(height[left] <= height[right]) {
if(count == 0) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
} else {
if(height[left] <= height[left + 1]) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
}
}
left++;
} else {
if(count == 0) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
} else {
if(height[right] <= height[right - 1]) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
}
}
right--;
}
}
return ans;
}
}
class Solution {
public int maxArea(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int ans = 0;
int count = 0;
while(left < right) {
if(count == 0) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
if(height[left] <= height[right]) {
left++;
}else{
right--;
}
} else{
if(height[left] <= height[right]) {
if(height[left] > height[left - 1]) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
}
left++;
} else {
if(height[right] > height[right + 1]) {
int area = Math.min(height[left], height[right]) * (right - left);
ans = Math.max(ans, area);
}
right--;
}
count++;
}
}
return ans;
}
}
执行用时分布
4ms
击败60.63%使用 Java 的用户
消耗内存分布
56.65MB
击败8.94%使用 Java 的用户
3.进阶100%
- 宽度小的容器容积比宽度大的容器大，他的高度一定更高，所以只找高度更高的。
class Solution {
public int maxArea(int[] height) {
int len = height.length;
int left = 0;
int right = len - 1;
int ans = Math.min(height[left], height[right]) * (right - left);
// 宽度小的容器容积比宽度大的容器大，他的高度一定更高
while(left < right) {
if(height[left] < height[right]) {
int minVlu = height[left];
while(left < right && height[left] <= minVlu) {
left++;
}
} else {
int minVlu = height[right];
while(left < right && height[right] <= minVlu) {
right--;
}
}
ans = Math.max(ans,Math.min(height[left], height[right]) * (right - left));
}
return ans;
}
}
执行用时分布
1ms
击败100.00%使用 Java 的用户
消耗内存分布
56.48MB
击败12.66%使用 Java 的用户
