300. Longest Increasing Subsequence

Leetcode

https://leetcode.com/problems/longest-increasing-subsequence/

題目

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

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.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

解答

• 方法一 - 動態規劃法

dp[i] 代表在 index 為 i 時，最長的子序列長度，但要怎麼求出 dp[i] 的數值呢？我們可以比較 nums[i] 跟之前 index 為 j 時數字的大小 (即比較 nums[i] 與 nums[j])，如果 nums[i] 的值比較大的話，就代表 dp[i] 可能的值為 dp[j] + 1 (這裡多加的長度 1 是因為 nums[i] 大於 nums[j])

例如：nums = [1, 7, 3, 4, 10, 5], 此時的 i = 3, nums[i] = 4

這時我們要做的是遍歷 i 之前的數組：

• j = 0, nums[j] = 1 < nums[i]

  所以 dp[4] 其中一個的可能值為 dp[0] + 1，dp[0] 前面會算過等於 1

  => dp[4] = 1 + 1 = 2，子字串為 [1, 4]

• j = 1, nums[j] = 7 > nums[i]

  因為 nums[i] 沒有比 nums[j] 大，所以 dp[4] 其中一個的可能值只有自己

  => dp[4] = 1，子字串為 [4]

• j = 2, nums[j] = 3 < nums[i]

  所以 dp[4] 其中一個的可能值為 dp[2] + 1，dp[2] 前面會算過等於 2

  => dp[4] = 2 + 1 = 3，子字串為 [1, 3, 4]

接著在每一輪的遍歷中找到這些 可能性的最大值 dp[i]，就是題目要求的答案

var lengthOfLIS = function (nums) {
    // 初始化所有 index 時，將最長的子字串預設為 1
    const dp = Array.from(Array(nums.length), () => 1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // 遍歷小於 len 的值，只要目前值大於 index 為 i 時的值，dp[i] = dp[j] + 1
            const newValue = nums[i] > nums[j] ? dp[j] + 1 : 1;
            dp[i] = Math.max(dp[i], newValue);
        }
    }

    // 最後求出所有 dp 中的最大值
    return Math.max(...dp);
};

Runtime: 144 ms, faster than 73.96% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.8 MB, less than 26.51% of JavaScript online submissions for Longest Increasing Subsequence.

Time complexity: 1+2+3+...+n = n(n+1)/2 => O(n^2)

Space complexity: the size of dp = O(n)

參考資料

300. Longest Increasing Subsequence · leetcodeleetcode.wang

• 方法二

這個方法有點不太直覺，下面我們直接用範例來看一下：

範例：nums = [3, 5, 6, 2, 4]

一開始先定義 arr = [nums[0]]，這個 arr 矩陣紀錄的是 最長子序列

• i = 1, nums[1] = 5

  因為 nums[1] 大於 arr[0]，直接加進矩陣後面

  => arr = [3, 5]

• i = 2, nums[2] = 6

  因為 nums[2] 大於 arr[1]，直接加進矩陣後面

  => arr = [3, 5, 6]

• i = 3, nums[3] = 2

  因為 nums[3] 小於 arr[1]，需要尋找矩陣中 剛好大於目前數字的元素(3) 並替換掉

  => arr = [2, 5, 6]

  (可以發現此時實際的最長子序列應該是 [3, 5, 6]，但因為題目只需要求得長度，所以即使紀錄的是[2, 5, 6]也沒有關係)

• i = 4, nums[4] = 4

  因為 nums[4] 小於 arr[2]，需要尋找矩陣中 剛好大於目前數字的元素(5) 並替換掉

  => arr = [2, 4, 6]

按照上面的邏輯算完後 arr = [2, 4, 6]，對應到實際上的最長子序列應該是 [3, 5, 6]，但因為答案只需求得 最長子序列的長度，所以計算 arr.length = 3 就可以了

var lengthOfLIS = function (nums) {
    const arr = [nums[0]];

    for (let i = 1; i < nums.length; i++) {
        const value = nums[i];
        // 如果目前數字大於 arr 中最大的數字，即代表最長的子字串可以加 1
        if (value > arr[arr.length - 1]) {
            arr.push(value);
        } else {
            // 尋找 arr 矩陣中剛好大於目前數字的元素，並替換掉它
            for (let j = 0; j < arr.length; j++) {
                if (value <= arr[j]) {
                    arr.splice(j, 1, value);
                    break;
                }
            }
        }
    }

    return arr.length;
};

Runtime: 132 ms, faster than 78.47% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.4 MB, less than 65.98% of JavaScript online submissions for Longest Increasing Subsequence.

Time complexity: O(n^2) - in the worst case

Space complexity: O(n)

參考資料

300. Longest Increasing Subsequence - LeetCode Solutionliweiwei1419.github.io

• 方法三

在方法二中，尋找 arr 矩陣中剛好大於目前數字的元素，並替換掉它 => 這一步驟是從頭開始遍歷 arr矩陣找到這個元素的，但剛好 arr 是從小到大已經排序過的矩陣，所以要找出其中 剛好大於目前數字的元素，最快的方式就是使用 binary search

var lengthOfLIS = function (nums) {
    const arr = [nums[0]];

    for (let i = 1; i < nums.length; i++) {
        const value = nums[i];
        if (value > arr[arr.length - 1]) {
            arr.push(value);
        } else {
            // 利用 binary search 找出剛好大於目前數字的元素
            let low = 0;
            let high = arr.length - 1;

            while (low < high) {
                const mid = Math.floor((low + high) / 2);
                if (value <= arr[mid]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            arr.splice(low, 1, value);
        }
    }

    return arr.length;
};

Runtime: 122 ms, faster than 79.87% of JavaScript online submissions for Longest Increasing Subsequence.

Memory Usage: 40.1 MB, less than 89.37% of JavaScript online submissions for Longest Increasing Subsequence.

Time complexity: O(n⋅log(n))

N - 先遍歷矩陣一次

log(n) - binary search

Space complexity: O(n)

測資

let nums = [10,9,2,5,3,7,101,18]; // 4
// nums = [0,1,0,3,2,3]; // 4
// nums = [7,7,7,7,7,7,7]; // 1
// nums = [4,10,4,3,8,9]; // 3
// nums = [6,7,9,4,10,5]; // 4

console.log(lengthOfLIS(nums))