[Leetcode]11: Container With Most Water

Link :https://leetcode.com/problems/container-with-most-water/

Problem :
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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.
找到最大長方形面積。使用兩個pointer來實作,計算每次的長方形面積大小,將比較矮的邊長往下一個位置移動(盡量保留較大的值)。

圖來自leetcode

Thoughts:
1. 使用兩個指針(right, left)來檢查哪裡是max_area。
2. 每次都先計算出當下的area,放到max裡面進行比較。
3. 計算完後完後開始移動指針,將較小的值往中間靠近。

Solution:

class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
left = 0
right = len(height)-1
while left<right:
tmp = min(height[left],height[right]) * (right-left)
max_area = max(max_area, tmp)
if height[left]<height[right]:
left += 1
elif height[left]>height[right]:
right-=1
else:
left+=1
right-=1
return max_area