给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
时间复杂度:O(n^2)
空间复杂度:O(1)
const getWater = function(heights){
let len = heights.length,maxArea = 0;
for(let p1 = 0;p1<len;p1++){
for(let p2 = p1+1;p2<len;p2++){
const height = Math.min(heights[p1],heights[p2]);
const width = p2 - p1
const area = height * width
maxArea = Math.max(maxArea,area)
}
}
return maxArea
}
时间复杂度:O(n)
空间复杂度:O(1)
const getWater = function(heights){
let len = heights.length,p1 = 0,p2 = heights.length -1,maxArea = 0;
while(p1<p2){
const height = Math.min(heights[p1],heights[p2])
const width = p2 - p1
const area = height * width
maxArea = Math.max(maxArea,area)
if(heights[p1]<=heights[p2]){
p1++;
}else{
p2 --
}
}
return maxArea
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。