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 ith 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軸找兩條線,找到組成一個可裝最多水的容器

回傳可裝最多水的容積

注意你不能傾斜容器

LeetCode #11 Constraints Pictures
題目約束

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

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

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

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

Example 1:

LeetCode #11 Example1 picture
官方範例圖
LeetCode #11 Example1

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

要注意的是左側的紅線(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差距

LeetCode #11 Example2

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

故回傳容積 ➔ 兩條線最低高度 : 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(n2)

很基礎的巢狀迴圈 ,看到 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讓我知道 !

最新文章

發佈留言

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