LeetCode0009

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/
駄目だろうな～と思いつつ，
最初，このように全探索での解放で行った．結果はもちろんTime Limit Exceededになった．

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans=0
        for i in range(len(height)):
            for j in range(len(height)):
                if i == j:
                    min = 0
                else:
                    min = height[i]
                    if min > height[j]:
                        min=height[j]
                    if ans <= min*abs(i-j):
                        ans=min*abs(i-j)
        return ans

全探索はn^2のおーだーになるので，時間が足りません．Greedy法を使ってr,lを狭めていきます．そして低いほうを更新していく方法でAccepted

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        l=0
        r=len(height)-1
        min_h=0
        while r > l:
            min_h = min(height[l],height[r]) 
            if ans <  min_h * (r-l):
                ans = min_h *(r-l)
            if height[l]> height[r]:
                r -=1
            else:
                l+=1
        return ans
    ```