題目:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

給定一個陣列,表示牆的高度,index則是它們的位置
找出在哪兩個牆中能裝最大面積的水(可忽略中間的牆),回傳該最大值

在兩牆間最大的裝水量
高會是其中較低的那面牆,否則水會溢出
寬則是兩者index相減
而我們就是要找出高x寬的最大值

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxvol=0
        l=0
        r=len(height)-1
        
        while True:
            if height[l]<=height[r]:
                maxvol=max(height[l]*(r-l),maxvol)
                l=l+1
            else:
                maxvol=max(height[r]*(r-l),maxvol)
                r=r-1
            if r==l:
                break
        
   
        return maxvol

設立兩個指標l,r,分別從陣列兩邊開始移動
紀錄l,r所在位置的牆會形成的裝水量
接著我們要移動指標
要增大裝水體積,我們自然會想要更高的高
因此我們會想要把矮的牆換掉去尋找另一面牆

換個角度,我們想想把高牆換掉的可能:
1.高牆依然比低牆高:高不變,寬變小
2.高牆變得跟低牆一樣高:高不變,寬變小
3.高牆變得比低牆矮:高變小,寬變小
沒有一個會帶我們找到更大的值
只改變矮牆的策略等同於忽略這些沒必要計算的可能

所以我們看兩面牆何者較矮,就移動該指標
去尋找我們下一個裝水量
途中紀錄到的最大裝水量就是我們要找的最大裝水量了
最後執行時間723ms(faster than 97.68%)

那我們下題見