最长递增子序列

题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

思路分析

我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值 ( 即在数组 1,2,3,4,5,6中长度为3的上升子序列可以为 1,2,3 也可以为 2,3,4 等等，但是d[3]=3，即子序列末尾元素最小为3 )。 用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1] = nums[0]。

我们依次遍历数组nums 中的每个元素，并更新数组 d 和 len 的值。如果 nums[i] > d[len] 则更新 len = len+1，否则在 d[1…len]中找满足 d[i−1] < nums[j] < d[i] 的下标 i，并更新 d[i]=nums[j]。
根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

最后整个算法流程为：

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：

• 如果 nums[i] > d[len] ，则直接加入到 d 数组末尾，并更新 len = len + 1；

• 否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]。

以输入序列 [0, 8, 4, 12, 2] 为例：

• 第一步插入 0，d=[0]；
• 第二步插入 8，d=[0,8]；
• 第三步插入 4，d = [0,4]；
• 第四步插入 12，d = [0, 4, 12]；
• 第五步插入 2，d = [0, 2, 12]。

最终得到最大递增子序列长度为 3。

// 新建数组 d，用于保存最长上升子序列。
// 对原序列进行遍历，将每位元素二分插入 d 中。
// 如果 d 中元素都比当前遍历的元素小，则将它当前元素插到d数组最后
// 否则，用当前元素覆盖掉d数组中比它大的元素中最小的那个。
// 总之，思想就是让 d 中存储比较小的元素。这样，d 未必是真实的最长上升子序列，但长度是对的。
var lengthOfLIS = function (nums) {
    let len = 1; // 变量 len 记录目前 d 数组中最长上升子序列的长度，起始时 len 为 1
    let tail = nums.length;
    if (tail === 0) return 0
    let d = []; // 数组 d ，用于维护最长上升子序列
    d[len] = nums[0]; // 起始时，令 d[1] = nums[0]
    for (let i = 1; i < tail; ++i) {
        if (nums[i] > d[len]) {
            // nums[i] > d[len] ，则直接加入到 d 数组末尾，并更新 len = len + 1
            d[++len] = nums[i];
        } else {
            let l = 1, r = len, flag = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 flag 设为 0
             // 在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]
            while (l <= r) {
                let mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
                    flag = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            d[flag + 1] = nums[i];
        }
    }
    return len;
};