这是我参与更文挑战的第 16 天，活动详情查看更文挑战

这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

124. 最长递增子序列 (longest-increasing-subsequence)

题目

这里不贴题了，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
复制代码

基本思路

先做个广告，我上上篇思维题很有意思，可以一看放松下脑子。 点击这里快速进入

动态规划问题久违了，如果对这个不熟悉，请先看看这篇动态规划思路

我们还是按照基本步骤来

寻找最优子结构(状态表示)
归纳状态转移方程(状态计算)
边界初始化

状态表示: dp[i] 为前i项最长上升子序列的长度, dp一定是升序的

状态转换: 在计算 dp[i] 之前，我们已经计算出 dp[0 ~ i−1] 的值，则状态转移方程为：

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

即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，那么 nums[i]必然要大于 nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。

边界条件: 初始长度就是本身长度为1

写法实现

var lengthOfLIS = function (nums) {
    if (!nums || !nums.length) {
        return 0
    }
    let dp = new Array(nums.length).fill(1)
    let max = 1
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // nums[i]要大于前面的一个数 nums[j]，才能放后面
            if (nums[i] > nums[j]) {
                // 状态转移
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
        // 选取最大值
        max = Math.max(max, dp[i])
    }
    return max
}

let nums = [10, 9, 2, 5, 3, 7, 21, 18]
console.log(lengthOfLIS(nums))
复制代码

125. 最长连续序列 (longest-continuous-increasing-subsequence)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
复制代码

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
复制代码

基本思路

有两种思路，第一种要求连续的数列，那么先排个序然后依次对比相邻元素就行，用一个 count 记录下连续的长度即可。
步骤如下：

先排序
声明历史最大值 max, 和当前长度 count
遍历数组，相邻元素相等就跳过，是连续的话 count++；要不就断了，count 置为 1
循环后使本轮 count 与 Max 对比取最大记录到 max

如果要令时间复杂度为 O(n)，就不能用排序。

另一种思路是

将数组元素存入 set 中, 利用 Set 去重先
检查每一项是否有比他小1的左边元素，有就跳过，因为他不是序列起点
找到每一个可能的起点并往右扩，找到最大长度，还是用 count 计数
接下来跟上面的方法基本一样，就是找寻边界用的是 Set 的 has()

写法实现

排序法

var longestConsecutive = (nums) => {
    // 先排序，但这样平均时间复杂度为 nlogn
    nums = nums.sort((a, b) => a - b)
    let [max, count] = [0, 1]
    for (let i = 0; i < nums.length; i++) {
        // 相邻元素相同跳过本轮循环
        if (nums[i] === nums[i+1]) {
            continue;
        }
        // 连续，count 就 + 1，否则就重置为 1
        if (nums[i] + 1 === nums[i+1]) {
            count++;
        } else {
            count = 1;
        }
        // 跟历史比较选取最大
        max = max > count ? max : count
    }
    return max
}
复制代码

Set去重后，利用映射找左右边界

var longestConsecutive = (nums) => {
    let res = 0
    // 利用 Set 去重
    let numsSet = new Set(nums)
    // 遍历每一个数，并往这个数的两边寻找相邻数
    for (let i = 0; i < nums.length; i++) {
        if (!numsSet.has(nums[i] - 1)) {
            let cur = nums[i]
            let count = 1
            while (numsSet.has(cur + 1)) {
                cur++
                count++
            }
            res = res < count ? count : res
        }
    }
    return res
}
复制代码

但此方法在 js 中速度反而慢于第一种。

另外向大家着重推荐下这个系列的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦点击此处交个朋友
Or 搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧