讓水槽裝最多的水 Container With Most Water_Leetcode 精選75題

Saj Shafique on Unsplash

題目敘述

題目會給我們一個隔板陣列height，代表每個隔板的高度，讓我們選取兩個隔板作為水槽的邊界，請問最多我們能裝多少水?

題目的原文敘述

測試範例

Example 1:

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.

Example 2:

Input: height = [1,1]
Output: 1

約束條件

Constraints:

• n == height.length

n代表輸入陣列height的長度。

• 2 <= n <= 10^5

height陣列長度介於2~10^5之間。

• 0 <= height[i] <= 10^4

每片隔板的高度介於0~10^4之間。

演算法

除了第一直覺的雙層暴力法(很有可能time-out 超過平台限制)之外，還有一個優雅的雙指針two-pointers的解法。

關鍵在於，存水的關鍵，在於左、右兩邊的隔板，哪邊比較矮，矮的隔板決定了能存多少水。

舉例來說: 假如底是w，左邊隔板高度是5，右邊的隔板高度是7，那麼可以儲存的水量就是w*(5,7) = 5w，因為，任何高度超過比較矮隔板的水流，最終都會溢流出去。

示意圖

image.png

image.png

因此，我們可以建造一個two pointers雙指針的迭代演算法。

令area = 橫截面面積 代表 儲水量的最大值，初始化為0

接著，left左指針初始化為0，代表最左邊的隔板index；right右指針初始化為n-1，代表最右邊的隔板。

每一回合迭代，就比較height[left], height[right]哪邊比較矮。

矮隔板的高度 * 當下的底

= 矮隔板的高度 * width

= 矮隔板的高度 * (right-left)

= 當下可以儲存的水量。假如比原本的儲水量還多，就更新為最大值。

然後，矮的那端往內收縮一格，假如右邊的隔板比較矮，就收縮右邊。同理，假如左邊的隔板比較矮，就收縮左邊。

如此反覆進行迭代，迴圈結束時，area 就代表整體儲水量的最大值。

程式碼

class Solution:
    def maxArea(self, height: List[int]) -> int:
        
        n = len(height)

        left, right = 0, n-1

        area = 0

        for width in range(n-1, 0, -1):

            if height[left] < height[right]:
                area = max( area, width * height[left] )
                left += 1
            
            else:
                area = max( area, width * height[right] )
                right -= 1
        
        return area

關鍵知識點

在於察覺存水多寡的關鍵，在於左、右兩邊的隔板，哪邊比較矮，矮的隔板決定了能存多少水。

複雜度分析

時間複雜度:

雙指針從頭尾兩端向中間收縮，所需時間為O(n)

空間複雜度:

只有使用到固定大小的臨時變數，所需空間為O(1)常數級別。

Reference:

[1] Container With Most Water - LeetCode