Leetcode — 300. Longest Increasing Subsequence (中文)

問題連結: https://leetcode.com/problems/longest-increasing-subsequence/

給予一個整數陣列 nums, 回傳在這個陣列中,我們可以找到最長的遞增子序列長度

子序列定義: 一個按照順序從array中抓幾個數字的序列, 子序列之中並不是每個數字都會被選擇進去, 但能保證的是每個數字的相對順序將與他們在原陣列的相對順序相同

條件:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

想法:

最初想法就是我們是否能用動態規劃dynamic programming來解決這題
會這樣想是因為既然我們不需真的回傳子序列的各個數字, 只需要知道最長長度, 代表我們不需真的知道這些子序列的內容, 只需要確定這個數字加進子序列時有合乎條件, 代表我們就可以延伸現有的子序列

⚠️把數字加進子序列的條件只有一個 - 只要想被加進來的數字比現有子序列的最後一個數字還大就可以了! 因為每次加進子序列的數字都必須排最後一個

因此, 我們必須都依賴前幾個位置可組成的最長子序列長度們, 來決定我們這個位置可組成的最長子序列長度
用一個陣列來記錄每個位置的數字當作某子序列的最後一個數字時 我們可以組成的最長子序列長度, 那我們就不必自己一個一個找成員組新的子序列了, 只要看我們可否"撿別人尾刀"

但因為每次都需要一一檢查現在位置的前面所有位置中可組成的最長子序列的長度, 因此時間複雜度將為O(n²)

以下為58ms的程式碼, 贏過49%的人-

public int lengthOfLIS(int[] nums) {
        int max = 1;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
            if(dp[i]>max)
                max = dp[i];
        }
        return max;
    }

Follow Up: Could you improve it to O(n log(n)) time complexity?

面試官在你開心地想到可以輕鬆用dp來解這題時潑了你這個冷水, 那我們來想想有沒有辦法可以更快速的解這題

在每輪幫位置i找最長長度時, 我們將會考慮i前面所有位置的子序列, 看我們可不可以安插nums[i]進去每個現有的子序列, 因此我們只能在 真的找到nums[i]可以放在哪個現有子序列中的時候, 才能得知我們在位置i時可得到的最長子序列長度

程式邏輯:

這次, 我們不再用陣列來儲存每個位置可組的最長子序列, 我們用一個陣列arr跟變數len來儲存遞增數列及現況可以找到最長子序列的長度
(代表著arr[0]~arr[len-1]為遞增數列,在這之後則是我們還沒放進的空位們)

我們將走訪每個在nums裡面的數字, 不停用二元搜索法(時間複雜度為lg(n))來尋找可以把現在位置的數字nums[i]塞進陣列arr的位置, 當我們發現現在數字比arr裡面的任何數字都還要大的時候, 代表我們可以擴展我們現有最長子序列的長度, 因此更新len

⚠️要注意: 陣列裡面裝的數字們 不是一直都是 "最長子序列", 我們能確定的只有…

1. 數字將會是由小排到大, 但並非一定符合子序列規定 (也就是arr[0]的數字雖然比arr[1]小, 但arr[0]可能在nums中出現的時機比arr[1]晚)
2. 長度變更時, 只能代表我們確定現在加進的數字nums[i], 真的是最長子序列中最大的數字, 只知道最長子序列裡面, 共有(len-1)個數字比nums[i]小且這些數字的組成是符合子序列規定的
3. 現在的陣列長度真的是我們目前可以找到最長子序列的長度

😕: 為何說裡面的數字們不會真的是最長子序列, 但又說長度是對的?

因為我們每次做的事情就是把目前的數字nums[i]塞進arr裡面, 找他最適合被放置的位置
我們最希望看到的, 就是我們可以一直發現nums[i]比在arr的所有數字都還要大, 進而讓我們需要拓展我們的陣列arr,
但不一定我們每次都這麼幸運, 而這會發生一個情況 - 我們會找到一個比nums[i]大, 又跟nums[i]差最近的數字, 把它的位置讓給nums[i], 因此原本排得好好的數字就這樣被取代了
造成原本真的是"子序列的陣列"不再按照原本在nums中的順序來排了, 但有一個好處是 "整體arr的數字會越來越小但又維持著最長子序列可有的長度", 代表下一個nums[i]比所有數字都還要大的機會因此提升

👷用下面例子來看我們怎麼更新我們的arr
假設nums = [10, 9, 2, 5, 3, 7, 20, 18, 4, 6, 8, 1, 0]

🔧Step 0. 初始狀態 arr為空, len為0, 代表我們還沒放任何數字進去arr

step 0 result

🔧Step 1. 現在數字:10, 我們來看10要如何放進arr中, 發現現在根本沒有數字在arr中可以比較, 因此我們直接把10放進arr的"最尾端" , 也因此arr擴增, len往上加1

step 1 result

🔧Step 2. 現在數字:9, 我們來看9要如何放進arr中, 發現9能放的位置跟10重疊, 因此我們直接取代10, arr沒能擴增, len不變

step 2 result

🔧Step 3. 現在數字:2, 我們來看2要如何放進arr中, 發現2能放的位置跟9重疊, 因此我們直接取代9, arr沒能擴增, len不變

step 3 result

🔧Step 4. 現在數字:5, 我們來看5要如何放進arr中, 發現5能放的位置是arr的最尾之後, arr成功擴增, len加1, 現在就是要維持著我們長度為2的遞增數列了

step 4 result

🔧Step 5. 現在數字:3, 我們來看3要如何放進arr中, 發現3能放的位置跟5重疊, 因此我們直接取代5, arr沒能擴增, len不變

step 5 result

🔧Step 6. 現在數字:7, 我們來看7要如何放進arr中, 發現7能放的位置是arr的最尾之後, arr成功擴增, len加1, 現在就是要維持著我們長度為3的遞增數列了

step 6 result

🔧Step 7. 現在數字:20, 我們來看20要如何放進arr中, 發現20能放的位置是arr的最尾之後, arr成功擴增, len加1, 現在就是要維持著我們長度為4的遞增數列了

step 7 result

🔧Step 8. 現在數字:18, 我們來看18要如何放進arr中, 發現18能放的位置跟20重疊, 因此我們直接取代20, arr沒能擴增, len不變

step 8 result

🔧Step 9. 現在數字:4, 我們來看4要如何放進arr中, 發現4能放的位置跟7重疊, 因此我們直接取代7, arr沒能擴增, len不變

step 9 result

🔧Step 10. 現在數字:6, 我們來看6要如何放進arr中, 發現6能放的位置跟18重疊, 因此我們直接取代6, arr沒能擴增, len不變

step 10 result

🔧Step 11. 現在數字:8, 我們來看8要如何放進arr中, 發現8能放的位置是arr的最尾之後, arr成功擴增, len加1, 現在就是要維持著我們長度為5的遞增數列了

step 11 result

🔧Step 12. 現在數字:1, 我們來看1要如何放進arr中, 發現1能放的位置跟2重疊, 因此我們直接取代2, arr沒能擴增, len不變

step 12 result

🔧Step 13. 現在數字:0, 我們來看0要如何放進arr中, 發現0能放的位置跟1重疊, 因此我們直接取代1, arr沒能擴增, len不變

step 13 result

👷完成! 最長子序列長度為我們在step11就找到的5

以下為2ms的程式碼, 贏過98% -

public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        int len = 0; 
        for(int cur: nums)
        {
            int indx = binarySearch(arr,cur,len);
            arr[indx] = cur;
            if(indx == len)
                len++;
        }
        return len;
    }
    public int binarySearch(int[] arr,int target,int n){
        if(n==0)
            return 0;
        int s = 0, e = n-1;
        while(s<e)
        {
            int mid = s + (e-s)/2;
            if(target == arr[mid])
                return mid;
            if(target > arr[mid])
                s = mid+1;
            else
                e = mid-1;
        }
        if(target > arr[s]) //we can expand arr
            return s+1; 
        else
            return s; //target replace original arr[s]
    }

👷但其實上面我解說的例子, 碰巧都在len改變的時候, 擁有著合格子序列, 因此我想加碼一個例子, 佐證在arr不是一直都有合格子序列 —

an extra example

我們可以看到在step A ~C, len 都有改變, 改變的瞬間 "恰巧" arr中都是合格的子序列

但你可以看到在step D, 因為3取代了4, arr已經不包含子序列了

而這樣的情況甚至持續到Step F, 我們新增的數字是10, arr擴展的瞬間, 當下的arr中的數字們[3, 6, 8, 10]並不是最長子序列!
我們實際增加的最長子序列應該是[4, 6, 8, 10], 但其實沒關係, 因為只要長度對就可以了, 我們是因為 我們確定有長度為3的子序列, 且他們都比10還小, 才把10加上去的 (因為若最長子序列中有比10還大的數字, 那我們根本不可能把10加到arr的尾端)