数组-盛最多水的容器
原创
给你 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
}方案二：双指针 利用while 实现双侧指针移动
时间复杂度：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 删除。
评论
登录后参与评论
推荐阅读