圈圈工程師

Change Change Developer

0%

Leetcode 筆記 - 圖解解題 Container With Most Water

發表於 更新於 分類於
Leetcode 筆記 - 圖解解題 Container With Most Water

題目

Leetcode 題目網址 🚐

範例

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

解題關鍵 1

  • 不管是左邊比較高還是右邊比較高，水位的面積高度只會到達較低的那個高度，例如：
    Alt text

在知道這個關鍵後，我們就可以先用暴力破解法得到答案：

1
2
3
4
5
6
7
8
def maxArea(height: List[int]) -> int:
    res = 0

    for l in range(0, len(height)):
        for r in range(l + 1, len(height)):
            area = (r - l) * min(height[l], height[r]) # 會選擇左右兩邊最小的原因：水位的面積高度只會到較低的那個高度
            res = max(res, area)
    return res

以下圖解暴力破解法的部分流程

圖解暴力破解法流程

因爲暴力破解法每次的 L 指標會跑到底（最右邊） N 次，因此時間複雜度會是 O(N^2)

可以在更好嗎？ 🙂

解題關鍵 2

  • 設定 L 指標爲 0，往右移動 ➡️ ；R 指標爲最右邊，往左移動 ⬅️
  • 因爲題目是要找出最大的面積，每次固定較大的那方，移動較小的那方，則有機會得到更大的水位面積
    • 例如當 L(1) vs R(7) 的時候，把 L ➡️ 有機會得到更大的水位面積；反之則是把 R ⬅️
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxArea(self, height: List[int]) -> int:
    
        L, R = 0, len(height) - 1
        res = 0

        while L < R:
            # 找出左邊與右邊比較小的一方，乘上左右中間的距離後的值
            # 如果有大於最大值則取代之
            res = max(res, min(height[L], height[R]) * (R - L))

            # 如果左邊小於右邊，左指針向右移動
            if height[L] < height[R]:
                L += 1
            # 如果左邊大於等於右邊，右指針向左移動
            else:
                R -= 1
        
        return res

以下圖解法的部分流程

經過雙指針從左右兩次往內包夾的優化解法後，就可以把時間複雜度降爲 O(N) 囉！

最後也感謝你的收看！🎉

參考