问题描述
来源:LeetCode第11题
难度:中等
给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
提示:
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
视频分析
代码部分
1,以当前柱子为桶的高度,分别从两边查找
public int maxArea(int[] height) {
int maxAre = 0;// 保存最大值
int left = 0;
int right = 0;
int length = height.length;
//以当前柱子为桶的左边界开始查找
while (left < length) {
// 从右边开始查找第一个不小于当前柱子的高度
right = length - 1;
while (left < right) {
if (height[left] > height[right]) {
right--;
} else
break;
}
//计算围成的面积
int are = height[left] * (right - left);
maxAre = Math.max(maxAre, are);
left++;
}
right = length - 1;
//以当前柱子为桶的右边界开始查找
while (right > 0) {
// 从左边开始查找第一个不小于当前柱子的高度
left = 0;
while (left < right) {
if (height[right] > height[left]) {
left++;
} else
break;
}
//计算围成的面积
int are = height[right] * (right - left);
maxAre = Math.max(maxAre, are);
right--;
}
return maxAre;
}
2,双指针
public int maxArea(int[] height) {
int maxAre = 0;// 保存最大值
int left = 0;
int right = height.length - 1;
while (left < right) {
maxAre = Math.max(maxAre, (right - left)
* Math.min(height[left], height[right]));
// 矮的柱子往中间靠
if (height[left] < height[right])
left++;
else
right--;
}
return maxAre;
}
3,双指针优化
public int maxArea(int[] height) {
int maxAre = 0;// 保存最大值
int left = 0;
int right = height.length - 1;
while (left < right) {
int minHeight = Math.min(height[left], height[right]);
maxAre = Math.max(maxAre, (right - left) * minHeight);
// 如果两个柱子往中间靠的时候,有更短的或一样高的,直接跳过
while (left < right && height[left] <= minHeight)
left++;
while (left < right && height[right] <= minHeight)
right--;
}
return maxAre;
}
写了600多道算法题解了,都是文字版的,对于新手可能不是太容易理解。最近考虑录一些视频版的,我对录屏这方面没有经验,初期的视频可能比较啰嗦,大家就凑合着看吧,等我练熟了就好了
联系客服