LeetCode 300：最长递增子序列题解

因为刚好最近在研究 Vue3 的原理，刚好涉及到 LIS 的内容，之前做题直接 DP 算出来就没继续研究了，Vue3 有用贪心的策略， 这边重新回来看下这个问题。

题目描述

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列不要求在原数组中连续，但需要保持原有的相对顺序。

例如：

const nums = [10, 9, 2, 5, 3, 7, 101, 18]

其中一个最长递增子序列是：

[2, 3, 7, 101]

所以答案是 4。

dp 思路

dp 思路比较简单， 很容易想到状态转移方程是：

    dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 num[j] < num[i]

实现代码是：

function lengthOfLIS(nums: number[]): number {
    const dp = [];
    for (let i=0; i<nums.length; i++) {
        let maxDp = 1;
        dp[i] = 1;
        for (let j=0; j<i; j++) {
            if (nums[j] >= nums[i]) {
                continue;
            }
            maxDp = Math.max(dp[j]+1, maxDp)
        }
        dp[i] = maxDp;
    }
    return Math.max(...dp);
};

贪心策略

大致思路是： 维护一个数组tails[i], 表示长度为 i + 1 的递增子序列中，末尾的最小元素

然后遍历 nums[i] 时，在 tails 上找到第一个大于 nums[i] 的位置，用 nums[i] 替换该值。如果所有元素都小于 nums[i] ，则 nums[i] 直接添加到 tails 后面。

最后，最长子序列的长度，就是 tails 的长度了。

然后，还可以优化下，找到第一个大于 nums[i] 的位置，可以用二分查找，这样整体的时间复杂度可以降低为 O(NlogN) 。

实现的代码是：

function lengthOfLIS(nums: number[]): number {
    if (nums.length ===0) {
        return 0;
    }
    const tails = [nums[0]];
    for (let i=1; i<nums.length; i++) {
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i]);
        } else {
            // 二分查找第一个大于nums[i]的
            let l = 0, r = tails.length-1;
            let pos = -1;
            while (l <= r) {
                let mid =  Math.floor((l + r) / 2);
                if (tails[mid] < nums[i]) {
                    l = mid +1;
                    pos = mid;
                } else {
                    r = mid -1;
                }
            }
            tails[pos+1] = nums[i];
        }
    }
    return tails.length;
};