# **Leetcode筆記(Container With Most Water)**

:::info
:information_source: 題目 : Container With Most Water, 類型 : arrays , 等級 : medium
日期 : 2023/02/22，2023/05/03，2023/06/27，2023/03/25，2024/10/02
:::

### 嘗試

值得鼓勵，想到two pointer法，思路也大致對，但實在不用l = i，時間複雜度O(n^2)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        for i, n in enumerate(height):
            r = len(height) - 1
            l = i
            while l < r:
                if height[r] >= height[l]:
                    area = height[l] * (r - l)
                    l += l
                else:
                    area = height[r] * (r - l)
                    r += r
                res = max(res, area)
                
        return res

2023/05/03

# 如果右邊比較高，代表右邊會是最有成功機率的一面牆，所以不能捨棄，故移動左邊牆

class Solution:
    def maxArea(self, height: List[int]) -> int:
        
        l, r = 0, len(height) - 1
        res = 0
        temp_height = 0

        while l < r:
            temp_height = min(height[l], height[r])
            res = max(res, temp_height * (r - l))
            # 如何決定要往左還是往右移
            if height[r] >= height[l]:
                l += 1
            else:
                r -= 1
        
        return res

2023/06/27

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

        while l < r:
            maxArea = max( maxArea, min(height[l], height[r]) * (r - l) ) 
            if height[l] > height[r]:
                r -= 1
            elif height[l] <= height[r]:
                l += 1
        
        return maxArea

2023/12/02

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxRes = float("-inf")
        l, r = 0, len(height) - 1
        while l < r:
            area = min(height[l], height[r]) * (r -l)
            maxRes = max(maxRes, area)
            # update the smallest boundary with the smallest heigth
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return maxRes

2023/03/25

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

        while l < r:
            maxRes = max(maxRes, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        
        return maxRes

2024/10/02

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

        while l < r:
            area = (r - l) * min(height[l], height[r])
            maxArea = max(maxArea, area)
            if height[l] > height[r]:
                r -= 1
            else:
                l += 1

        return maxArea

---
### **優化**

時間複雜度O(n)

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

        while l < r:
            area = min(height[l], height[r]) * (r - l)
            res = max(res, area)
            if height[r] >= height[l]:
                l += 1
            else:
                r -= 1
 
        return res

---

**:warning: 錯誤語法**
:::warning
Time Limit Exceeded可能是用太多時間(錯的方法)去跑
r -= 1 是減不是加，還有不是r -= r
:::

**:thumbsup:學習**
:::success
可以被簡化在一個min中選擇area = min(height[l], height[r]) * (r - l)
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=UuiTKBwPgAo
Provided by. NeetCode

###### tags: `arrays` `medium` `leetcode`