难度:Medium
题目:
给定一个长度为
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 <= 105
0 <= height[i] <= 104
Related Topics
- 贪心
- 数组
- 双指针
重点!!!解题思路
第一步:
明确解题手段:此题可以使用双指针这种比较简单的方法
第二步:
在容器两边向内进行比较,每次比较选出此时容器存水的最大值
源码+讲解:
class Solution {
public int maxArea(int[] height) {
int ans=0,i=0,j=height.length-1;
while (i<j){
ans=Math.max(ans,(j-i)*Math.min(height[j],height[i])); //每次选最小的那条线作为高
if (height[i]<height[j]){ //左面如果比右面矮 就让左面再往后面走走看
i++;
}else{ //右面同理
j--;
}
}
return ans;
}
}
运行结果:
文章来源:https://www.toymoban.com/news/detail-547868.html
系列持续更新中,喜欢练习算法的那就点个攒吧 文章来源地址https://www.toymoban.com/news/detail-547868.html
到了这里,关于LeetCode[11]盛水最多的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!