11. 盛最多水的容器
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例:
解题思路
- 暴力穷举法
class Solution:
def maxArea(self, height: List[int]) -> int:
maxarea = 0
for l in range(len(height)):
if height[l]*(len(height)-1-l) < maxarea:
continue
for r in range(l+1,len(height)):
maxarea = max(maxarea, min(height[l],height[r])*(r-l))
return maxarea
#这种方法我提交一直显示超时,没有想到更好的优化方法,如果读者有谁想到欢迎在评论里面指出。
- 容器面积的height受最短边的影响,开始从最外围开始遍历,然后逐步从短边到长边遍历,保存每次遍历围成的矩阵的面积即可
class Solution:
def maxArea(self, height: List[int]) -> int:
l = 0
r = len(height)-1
maxarea = 0
while(l<r):
maxarea = max(maxarea,min(height[l],height[r])*(r-l))
if height[l]<height[r]:
l+=1
else:
r-=1
return maxarea
网友评论