題目出處

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

難度

Medium

題目分類

Array, TwoPointers

題外話

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

個人範例程式碼 – 2022/5/12 二刷

class Solution:
    def maxArea(self, height: List[int]) -> int:
        if not height or len(height) < 2:
            return 0

        start, end = 0, len(height)-1
        # [1,8,6,2,5,4,8,3,7] = 7(8-1)*7(min([8],[1]))
        max_water = 0
        while(start < end):
            max_water = max(max_water, (end - start) * min(height[start], height[end]))
            if height[start] < height[end]: # try to find two highest side
                start += 1
            else:
                end -= 1
        else:
            max_water = max(max_water, (end - start) * min(height[start], height[end]))

        return max_water

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

策略是，想辦法找到左右都是最高的，只去移動(更新)邊比較小的那側。
利用 two pointer 去找，過程中不斷更新。

input handling

如果 not height or len(height) < 2，return 0 (錯誤的狀況)

Boundary conditions

用 while(start < end) 控制搜尋的範圍。

個人手繪解法筆記 (解法重點) – 2021/3/31 一刷

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

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

• 装最多水的容器 · Container With Most Water
• https://leetcode.com/problems/container-with-most-water/discuss/1069698/Python-O(n)-by-two-pointers-w-Comment