0%
Loading ...

【Leetcode 筆記】 11. Container With Most Water

image 1721120448981

題目解釋

給定一個長度為 n 的整數 array。
第 i 條線的兩個端點為 (i, 0)(i, height[i])
回傳 container 可以儲存的最大水量。

範例

file

  • 輸入: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
  • 輸出: 49

在這種情況下,容器可容納的最大水面積(藍色部分)為 49。

最佳解法

步驟

  1. 令雙指標 leftright
  2. 如果現在的乘積 curr_areamax_area 小,就移動 height[left]height[right] 中比較小的那個
  3. 開心回傳 max_area

程式碼

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

        while (left < right):
            min_bar = min(height[left], height[right])
            curr_area = (right - left) * min_bar
            max_area = max(curr_area, max_area)

            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return max_area

時間複雜度

O(n),n 是 height 的元素個數。

空間複雜度

O(1)

結語

只有我每次第一眼看到題目都會想說為啥不是 88 配嗎…。
( 論國小面積公式沒學好的下場 😅 )

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.