LeetCode:(Python)(Arrays) Container With Most Water

題目連結：https://leetcode.com/problems/container-with-most-water/description/

題意說明：

題目給予一個數字 array，裡面的數字可以想成高度，排序代表位置。

要找出哪兩個數字高度可以組成最大的面積

（真）初始想法

第一個數字是 1，第二個是 8，面積是 1

地三個數字是 6，1*2 和 6*1比

光想到這裡就覺得不可行，繼續往後走，要比對的組合會越來越多

初始想法

真理在兩個極端之間，如果我有兩邊往內走，一步一步找，應該就有機會找到最佳解

Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if len(height) == 1:
            return 0

        start = 0
        end = len(height)-1
        max_area = 0
        decrease_start = True
        while end > start:
            current_area = min(height[start],height[end])*(end-start)
            print("start:",start,",end:",end,",current_area:",current_area)
            max_area = max(max_area, current_area)

            if decrease_start:
                start += 1
                decrease_start = False
            else:
                end -= 1
                decrease_start = True
        return max_area

在 Test Case能跑，但 Submit過不了。

原因主要是我往內收斂的方式出問題，我的作法是無腦往內，我第一次左邊往內，第二次就右邊往內，沒有考慮數字大小等條件。

參考其他人作法

解法連結： https://leetcode.com/problems/container-with-most-water/solutions/2847080/python-mad-easy-100-on-god/?orderBy=hot&languageTags=python3

當左邊數字比較小，就左邊往內收一格

當右邊數字比較小，或是左右數字相同，就右邊往內收一格

這個方法之所以合理是因為

• 數值比較少的數字往內收，更有可能遇到比較大的數字，讓總面積提昇
• 有非常大的機會，最大面積會是由最大和次大的兩個數字包圍而成
• 如果不是由最大和次大的數字包含而成，那一定會是由較小的數字 + 非常常的距離組成

code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0
        end = len(height)-1
        max_area = 0

        while end > start:
            current_area = min(height[start],height[end])*(end-start)
            #print("start:",start,",end:",end,",current_area:",current_area)
            max_area = max(max_area, current_area)

            #print("height[start]:",height[start],",height[end]:",height[end])
            if height[start]<height[end]:
                start += 1
            else:
                end -= 1
                
        return max_area

跑起來的效能不佳，重新檢視後發現用 if來比較大小比 max快

code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0
        end = len(height)-1
        max_area = 0

        while end > start:
            current_area = min(height[start],height[end])*(end-start)
            #print("start:",start,",end:",end,",current_area:",current_area)
            if current_area > max_area:
                max_area = current_area

            #print("height[start]:",height[start],",height[end]:",height[end])
            if height[start]<height[end]:
                start += 1
            else:
                end -= 1
                
        return max_area