➣ Reading Time: 5 minutes

題目出處

https://leetcode.com/problems/container-with-most-water/

難度

Medium

題目分類

Array, TwoPointers

題外話

這題與 [42] Trapping Rain Water 類似,但 42 題比較難,
或是我有想過如果水缸換成「中柱隔開不計算」,搞不好都是另外一種更難的題目。

個人手繪解法筆記 (解法重點)

也因為「即使中柱隔開,照樣計算」,所以我們只要找到「兩側最高」乘上「寬度」綜合起來最大就是答案。

TwoPointers

我們用兩個指標 r, l 分別一個從左邊掃,一個從右邊掃,
從 height[r], height[l] 選比較矮的,往前走尋找更高的
(往前走也就是:r-1, l+1)

注意:我們定義的 r, l 是 「index」
而 height[r], height[l] 才是真正的「高」
(第一個自己 debug 就是發現這個錯誤XDD)

每算一次更新一次最大面積 (還好這題不用考慮中間有卡柱子的問題,簡單很多),
掃到中止目標 (寬 = 0 或 r 小於等於 l)

說「小於等於」是考慮所有「不可能」的情況,所以不只說等於

個人範例程式碼

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        l = 0 # index
        r = len(height)-1 # index
        width = len(height)-1
        while(width > 0 and l < r): # normal case
            area = width * min(height[r], height[l])
            # print(f"area = {area}, r = {r}, l = {l}") # debug
            max_area = max(max_area, area)


            # update
            if height[r] > height[l]: # l smaller
                l += 1
                width -= 1
            else:
                r -= 1
                width -= 1

        return max_area

Reference

https://leetcode.com/problems/container-with-most-water/discuss/1069698/Python-O(n)-by-two-pointers-w-Comment

⭐Python leetcode 相關文章整理⭐:
⭐Leetcode 解題紀錄⭐:難度Tag
⭐面試最經典 Top 75 題⭐:
1.【Leetcode】python - [1] Two Sum 兩數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼)#Easy#Array #HashTable
3.【Leetcode】python - [3] Longest Substring Without Repeating Characters 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#HashTable #TwoPointers #String #SlidingWindow
5.【Leetcode】python - [5] Longest Palindromic Substring 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#String #DP
11.【Leetcode】python - [11] Container With Most Water 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
15.【Leetcode】python - [15] 3Sum 三數之和 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Medium#Array #TwoPointers
48.【Leetcode】python - [48] Rotate Image 旋轉矩陣 個人手繪解法筆記與解題思考建議 (只講解法重點, 內含範例程式碼)#Medium (但我覺得很難)#Array
104.【Leetcode】python - [104] Maximum Depth of Binary Tree 個人手繪解法筆記 (只講解法重點, 內含範例程式碼) #Easy#Tree #DFS #Recursion
⭐Leetcode 小技巧⭐:
1.【Python】python 測試程式 – 利用 doctest 測試 python testcase 的優雅寫法,適用於 leetcode (doctest in function,搭配 function 的用法)
2.【Leetcode】python – 利用 doctest 測試 leetcode python testcase 的優雅寫法 (doctest in class,搭配 class 的用法)
⭐【喜歡我的文章嗎? 幫忙按讚除了鼓勵外,我也會將部分所得捐出!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免費註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,扣除掉網站本身經營的成本 (可惜目前還是虧本的),我會將 【50% 收益全部捐出】 並公開發文,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps