一、题目
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 and n is at least 2.
题目的意思就是给定 n 个非负整数,a1,a2,,,,,,an,其中每一个数代表一个点的坐标(i,ai)。n个垂直线段例如线段的两个端点在(i,ai)和(i,0)。找到两个线段,与 x 轴形成一个容器,使其包含最多的水。
二、思路
暴力求解即两层循环,会超时,而且也没什么意义,我们想其实包含水的多少取决于两条线段中较短的那个,可以分别在头尾设置两个指针,每次移动较短的那个,此题的思路跟很多题类似。但是证明略难,文末的博客中其实给了比较详细的证明,有兴趣可以看看。
三、代码
def maxArea1(height):
"""
:type height: List[int]
:rtype: int
"""
maxWater = 0
left,right = 0,len(height)-1
while(left < right):
maxWater = max(maxWater,min(height[left],height[right])*(right-left))
if height[left] < height[right]:
left+=1
else:
right-=1
print(maxWater)
return maxWater
if __name__ == '__main__':
height = [2,4,6]
maxArea1(height)
参考博客:https://segmentfault.com/a/1190000008824222