300.最长递增子序列

题目描述：

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

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

测试用例：

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

解题思路

贪心算法

维护一个二维数组 results。results[i]表示长度为 i+1 的递增子序列中，那个最有潜力继续增长的序列
遍历nums过程中，把 results 每一行的最后一项tail进行比较。
- 如果num(nums的每一项)比tail大，直接追加替换
- 反之，如果一路比到了第一项，再替换

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  if (nums.length === 0) return [];
  const results = [[nums[0]]];
  for (let i = 1; i < nums.length; i++) {
    let n = nums[i];
    update(n);
  }
  // console.log(results);
  // 更新序列的函数
  function update(n) {
    // 从后往前遍历现有序列
    for (let i = results.length - 1; i >= 0; i-- ) {
      const line = results[i];
      const tail = line[line.length - 1];
      if (n > tail) {
        // 可以扩展：创建新的更长序列
        results[i + 1] = [...line, n];
        break;
      } else if (tail > n && i === 0) {
        // 比所有序列末尾都小：替换最短序列
        results[i] = [n];
      }
      // 注意：如果 n === tail，什么也不做（严格递增）
    }
  }
 
  return results[results.length - 1].length;
};
// console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));
console.log(lengthOfLIS([10,9,2,5,3,7,101,18));

算法执行流程示例

以 [10, 9, 2, 5, 3, 7, 101, 18] 为例：

初始10：results = [[10]]
处理 9：9 > 1 且是第一项，替换序列 → [[9]]
处理 2：2 < 9 且是第一项，替换序列 → [[2]]
处理 5：5 > 2，扩展序列 → [[2], [2, 5]]
处理 3： 3 < 5 但 3 > 2，替换 → [[2], [2, 3]]
处理 7：7 > 3 ，扩展序列 → [[2], [2, 3], [2, 3, 7]]
处理 101：101 > 7，扩展序列 → [[2], [2, 3], [2, 3, 7], [2, 3, 7, 101]]
处理 18：18 < 101 ，替换合适序列 → [[2], [2, 3], [2, 3, 7], [2, 3, 7, 18]]

最终结果：最长序列长度为 4 [2, 3, 7, 18]

复杂度分析

时间复杂度：O(n²)

需要遍历数组中的每个元素：O(n)
对于每个元素，最坏情况下需要遍历所有现有序列：O(n)
总时间复杂度：O(n²)

空间复杂度：O(n²)

存储所有可能的递增子序列
最坏情况下，每个元素都可能产生新的序列

算法优化方向

当前算法可以优化到 O(n log n)：

function lengthOfLISOptimized(nums) {
  if (nums.length === 0) return 0;
  
  const tails = [nums[0]];  // 只存储每个长度的最小末尾值
  
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i];
    
    if (num > tails[tails.length - 1]) {
      tails.push(num);
    } else {
      // 二分查找替换位置
      let left = 0, right = tails.length - 1;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (tails[mid] < num) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tails[left] = num;
    }
  }
  
  return tails.length;
}

总结

关键点：

贪心策略：对于相同长度的子序列，保留末尾最小的
动态维护：不断用更有潜力的序列替换现有序列
倒序遍历：从长到短检查，找到第一个可以扩展的位置

算法的本质：

不是直接找最长序列，而是维护每个长度的最优候选
通过不断优化候选序列，最终得到最长长度

应用场景：

数据序列分析
任务调度
游戏中的升级路径规划

Dong 的笔记

探索