【LEETCODE】11-Container With Most Water [Python]
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個の非負の整数a 1,a 2,...,an,各座標を表す点(i,ai).
n本の線を引いて、line i接続(i,ai)and(i,0)
2本の線を見つけて、x軸と1つの容器を構成して、この容器が最も多くの水を盛ることができることを満たします
考え方:
要求容器の容量はmin(height[p 1],height[p 2])*(p 2-p 1)に依存する.
重要な問題は短板で、もちろん2板の間の距離もありますが、短板は移動の判断条件として、短板をもっと高くすることを目的としています.
二つの針はそれぞれ首の尾から真ん中に縮んで、どの板がもっと短いか、移動します.
面積はもっと広い面積しか記録されていません
参照先:
http://segmentfault.com/a/1190000003815582
Python
Note: You may not slant the container.
タイトル:
n個の非負の整数a 1,a 2,...,an,各座標を表す点(i,ai).
n本の線を引いて、line i接続(i,ai)and(i,0)
2本の線を見つけて、x軸と1つの容器を構成して、この容器が最も多くの水を盛ることができることを満たします
考え方:
要求容器の容量はmin(height[p 1],height[p 2])*(p 2-p 1)に依存する.
重要な問題は短板で、もちろん2板の間の距離もありますが、短板は移動の判断条件として、短板をもっと高くすることを目的としています.
二つの針はそれぞれ首の尾から真ん中に縮んで、どの板がもっと短いか、移動します.
面積はもっと広い面積しか記録されていません
参照先:
http://segmentfault.com/a/1190000003815582
Python
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
if height==[]:
return 0
l=len(height)
ans=0
p1=0
p2=l-1
while p1<p2:
ans=max(ans,min(height[p1],height[p2])*(p2-p1))
if height[p1]<height[p2]:
p1+=1
else:
p2-=1
return ans