Rain9Rain9
首页
AI 岗位
AI 目录
前端
后端
桌面端
WebGL
Web3
  • 算法与面试
  • 面试八股
  • Vim 练级
  • Github
  • 掘金
  • 公众号《与 IT 有约》
首页
AI 岗位
AI 目录
前端
后端
桌面端
WebGL
Web3
  • 算法与面试
  • 面试八股
  • Vim 练级
  • Github
  • 掘金
  • 公众号《与 IT 有约》
  • 算法与面试

    • 数据结构与算法
    • 数据处理手写题
    • JS 手写题
    • leetcode
    • 链表
    • 输出题
    • 场景应用
    • 各种排序
    • 高频算法模板速查(JS 版)

leetcode

1. 300. 最长递增子序列

给你一个整数数组 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

提示:

1 <= nums.length <= 2500 -104 <= nums[i] <= 104

进阶:你能将算法的时间复杂度降低到 O(n log(n)) 吗?

var lengthOfLIS = function (nums) {
    const len = nums.length
    if(len<=1) return len
    const dp = new Array(len).fill(1); // 初始化 dp
    for (let i = 0; i < len; i++) {
        // i与i前面的元素比较
        for (let j = 0; j < i; j++) {
        // 找比i小的元素,找到一个,就让当前序列的最长子序列长度加1
        if (nums[i] > nums[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        }
    }
    // 找出最大的子序列
    return Math.max(...dp);
};
最近更新: 2026/10/31 10:01
上一篇
JS 手写题
下一篇
链表