Try   HackMD

Leetcode 11. Container With Most Water

給定一個有n個非負的數字的數組 height 其索引代表x軸,數值代表y軸,找到一組n[left],n[right]使其形成的面積為最大的。

想法

(1)使用暴力解 (使用python3 TLE)

使用兩個迴圈比對每一個索引,回傳最大值

程式碼:

def maxArea(self, height: List[int]) -> int:
        ans = 0
        length = len(height)
        for i in range(length):
            for j in range(i+1,length):
                ans = max(min(height[i],height[j])*(j-i),ans)
        return ans

(2)使用兩個指針

使用兩個指針分別從開頭和結尾開始,兩者較小的轉換為下一個,依次算出結果。
例如:
n = 5
height = [1,3,5,6,8]
left = 0
right = n-1
當 hegiht[left]>height[right]則移動right為right-1
否則則移動left為left+1 直到right<left。

程式碼:

def maxArea(self, height: List[int]) -> int:
        ans = 0
        left = 0
        right = len(height)-1
        while(right>left):
            if(height[right]>height[left]):
                ans = max(ans,height[left]*(right-left))
                left+=1
            else:
                ans = max(ans,height[right]*(right-left))
                right-=1
        return ans