最长递增子序列

在研究学习 Vue3 的框架原理时学习到了 Vue3 的 diff 算法，在 diff 算法的实现中用到了 寻找最长递增子序列（LIS）的算法，觉得这个算法很有意思，于是准备实现一下。

具体实现

寻找最长递增子序列代码实现：

function lis(list) {
    if (!list || !list.length) {
        return 0
    }

    //设置结果集合，取 list 中的第一个值作为 result 的第一个默认值
    const result = [list[0]]

    //查找 result 中第一个大于给定数字的值的索引
    const findBigger = (num) => {
        for (let i = 0; i < result.length; i++) {
            if(result[i] >= num){
                return i
            }
        }
    }

    //因为已经取了 list 的第 1 项到 result 集合中，所以从 1 开始遍历 list
    for (let i = 1; i < list.length; i++) {
        //如果 list 中当前元素大于 result 的最后一个元素，那么说明 list 当前元素满足递增条件，加入到 result 集合中
        if (list[i] > result[result.length - 1]) {
            result.push(list[i])
        }
        else {
            //否则从 result 集合中找到第一个大于 list 当前元素的值的索引，然后进行替换
            const index = findBigger(list[i])
            result[index] = list[i]
        }
    }

    return result
}

//使用
const nums = [10, 9, 2, 5, 3, 7, 101, 18]
console.log(lis(nums))  //输出：[2, 5, 7, 18]