LeetCode --- 11. Container With Most Water

2018-08-17 0条评论 250次阅读 0人点赞

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container

题解

题目大意：给定n个数a1~an，代表垂直x轴的线的高度。求任意两条线之间所能装水的最大容积。容积的计算方式为 min(ai,aj) * (j – i) , i < j

def maxArea(height):
"""
:type height:
:rtype:
"""
ans = 0
l = 0
r = len(height) - 1
while l < r:
ans = max(ans,(r-l)*min(height[l],height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return ans

def maxArea(height):

"""

:type height:

:rtype:

"""

ans = 0

l = 0

r = len(height) - 1

while l < r:

ans = max(ans,(r-l)*min(height[l],height[r]))

if height[l] < height[r]:

l += 1

else:

r -= 1

return ans

很明显不是最优解

最优解

def maxArea(height):
"""
:type height:
:rtype:
"""
ans = 0
l = 0
r = len(height) - 1
while l < r:
ans = max(ans,(r-l)*min(height[l],height[r]))
if height[l] < height[r]:
l += 1
else:
r -= 1
return ans