LeetCode #11 Container With Most Water 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

中文翻譯

給予一個長度為n的整數陣列(高度)，總共有n列垂直的線，第i列垂直的線是由兩個端點組成，分別是 (i,0)跟(i,高度陣列[i])

從x軸找兩條線，找到組成一個可裝最多水的容器

回傳可裝最多水的容積

注意你不能傾斜容器

第一點題目中就有提到了，陣列長度為 n

長度n 介於 2 到 10⁵ 之間 ➔ 不用擔心連兩條線都沒有，組不成容器(<2的情況)

陣列中的整數介於 0 到 10⁴ 之間

下面來看下範例，不然單看題目敘述確實霧颯颯的

Example 1:

第一個範例我們可以看到，標示出來的兩條線即為可裝最多水的方式

要注意的是左側的紅線(index 1)高度為 8 ，右側紅線 (index 8)的高度僅為 7

要組成容積自然要用比較小的高度，不然水會溢出

以index 0 跟 index 1 的高度為例

分別為 1 跟 8，距離為1 ，計算容積➔ 兩條線最低高度 : 1 * 兩條線距離(index差) :1 = 1*1 = 1

可以看到第一條線跟第二條線只能組成容積為1的答案

那如果我們拿最高的兩條呢，分別是 index 1 (高度8) 及 index 6 (高度8)

計算如下 ➔ 兩條線最低高度 : 8 * 兩條線距離(index差) :5 = 8*5 = 40

可以看到，也不如已知答案的 49 ➔ 可以先假設最高的兩條也不一定為答案，因為還要考慮index差距

第二個範例比較沒什麼意思，總共只有兩條線，不想選也得選

故回傳容積 ➔ 兩條線最低高度 : 1 * 兩條線距離(index差) :1 = 1*1 = 1

解題思路

相信很多人第一個看到題目，想到的就會是用兩個遞迴迴圈來跑吧(至少筆者是這樣的…)

我們來看一下怎麼呈現吧

C# 解決方案

方案1 – 巢狀迴圈 (最直覺但不推薦，效能上不太行)

public class Solution {
    public int MaxArea(int[] height) {
     
        int l = height.Length;
        int max = 0;       //目前最大面積
        int maxH = -1;     //i 的最高高度
        
        for(int i = 0; i<l-1;i++)
        {
            if(height[i] < maxH)
            {
                continue;    
            }
            
            for(int j =i+1; j<l;j++)
            {
                int cal = Math.Min(height[i],height[j]) * (j-i);    //兩條線高度取其低 * index差
                if(cal>max)
                {
                    maxH = height[i];
                    max = cal;
                }
            }
        }
        
        return max;
    }
}

時間複雜度 : O(n²)

很基礎的巢狀迴圈 ，看到 i 跟 j 的時候應該就猜到了吧哈哈

這裡可以注意到多用了一個 maxH 來儲存目前最大容積的 i 高度(第一條的高度)

maxH 為目前最大值的i 高度，要是判斷下次迴圈時， i高度沒有高於maxH，就直接跳過

提交LeetCode執行速度約為 500~700ms左右，算是挺糟糕的

⭐方案2 – 推薦寫法，two pointer 前後收斂

過了一陣子之後，在回顧寫過的題目時，實在是嚥不下那口氣

苦思冥想過後，又更新了寫法，依然用兩個參數 i跟j，但不做兩次遞迴，改用前後收斂的方式

public class Solution {
    public int MaxArea(int[] height) {
     
        int i = 0;                //index的前收斂值
        int j = height.Length-1;  //index的後收斂值
        int maxAmt = 0;
        int iH;
        int jH;
        int cal;
        
        while(j>i)
        {
            iH = height[i];
            jH = height[j];
            
            //從前後開始收斂
            //哪一邊比較高，下次就收斂另一邊，一樣的話我們就委屈 i 一點吧
            if(iH>jH)
            {
                cal = jH*(j-i);
                j--;
            }
            else
            {
                cal = iH*(j-i); 
                i++;
            }
            
            if(cal>maxAmt)
                 maxAmt = cal;
            
        }
        return maxAmt;
    }
}

時間複雜度 : O(n) ➔ 次數只需跑 height.Length-1次，前後收斂到 j=i就結束

這個寫法的核心就在於

• 先從index的距離下手，通常來說，index距離越大，越有可能出現比較高的容積
• 哪一邊比較高，下次就收斂另一邊 ➔ 另一邊下次若比當前高，則有機會出現更高的容積

改為這種判斷方式之後，運行速度降至約 170~280ms，約為總體C#速度的前50%到90%了

Java解決方案

方案1

class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length-1;
        int maxAmt = 0;
        int iH;
        int jH;
        int cal;
        
        while(j>i)
        {
            iH = height[i];
            jH = height[j];
            
            //Convergence back and forth
            //which is higher，than will convergence from  the other side
            if(iH>jH)
            {
                cal = jH*(j-i);
                j--;
            }
            else
            {
                cal = iH*(j-i); 
                i++;
            }
            
            if(cal>maxAmt)
                 maxAmt = cal;
            
        }
        return maxAmt;
    }
}

Python3 解決方案

方案1

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0;
        j = len(height)-1;
        maxAmt = 0;
        
        while(j>i):
            iH = height[i];
            jH = height[j];
            
            if(iH>jH):
                cal = jH*(j-i);
                j-=1;
            else:
                cal = iH*(j-i); 
                i+=1;
            
            if(cal>maxAmt):
                 maxAmt = cal;
 
        return maxAmt;

JavaScript 解決方案

方案1

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var i = 0;
    var j = height.length-1;
    var maxAmt = 0;
    var iH;
    var jH;
    var cal;

    while(j>i)
    {
        iH = height[i];
        jH = height[j];


        if(iH>jH)
        {
            cal = jH*(j-i);
            j--;
        }
        else
        {
            cal = iH*(j-i); 
            i++;
        }

        if(cal>maxAmt)
        {
            maxAmt = cal;  
        }
    }
    return maxAmt;
};

結論

這題被歸類在LeetCode中階的題目中，但其實解法也不算複雜(就算暴力計算也能得到結果)

但 two pointer 這個寫法可以大大減少時間的消耗，之後在Array類的題目都會蠻常有他出場的機會

"竹外桃花三兩枝，春江水暖鴨先知"
                                                                                                                     蘇軾                             

題目連結 : Container With Most Water – LeetCode

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我點個廣告可以讓我不用擔心下個月的主機費 ε٩(๑> ₃ <)۶з

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

最新文章

• LeetCode #242 Valid Anagram 正確的易位構詞遊戲
• LeetCode #202 Happy Number 快樂號碼
• LeetCode 介面改版前後的使用體驗對比
• LeetCode #21 Merge Two Sorted Lists 合併兩個已排序的鏈結串列
• JavaScript 陣列尋找完美匹配：Every與Some的比較