最长递增子序列

LeetCode 题目 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)) 吗?

题目解析

题目中求的是最长增长子序列，如 [1,5,2,3], 最长增长子序列是[1,2,3]，长度是 3。也就是挑最长的递增子序列。

解题思路

动态规划

1. 定义状态：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度
2. 转移方程: 遍历 i 之前的数字，如果 数字比 i 小，dp[i] = max(dp[i], dp[j] + 1)
3. 初始化：dp[0] = 1

代码实现

var lengthOfLIS = function (nums) {
  // 数组长度
  const len = nums.length;
  // 动态规划缓存
  const dp = new Array(len).fill(1);
  // 遍历字符串 从 1 开始，因为 0 是确定一个，不需要计算
  for (let i = 1; i < len; i++) {
    // 往前退 对比之前
    let j = i - 1;
    // max 初始值 0 方便后续 dp 的计算
    let max = 0;
    // 往前找是否有比当前数字小的
    while (j >= 0) {
      // 如果找到了，取最大值的那一个 dp[j]
      if (nums[i] > nums[j]) {
        max = Math.max(max, dp[j]);
      }
      j--;
    }
    // 由于 max 初始值0，即使没有 max 也默认 1
    dp[i] = max + 1;
  }
  // 返回最大值
  return Math.max(...dp);
};

上面的解法复杂度是 O(n^2)，可以优化到 O(n log(n))。

二分查找 + 贪心

function lengthOfLIS(nums) {
  // 初始化结果数组，包含第一个元素
  const res = [nums[0]];
  let start, end, mid;
  
  // 遍历数组中的每一个元素
  for (let i = 1; i < nums.length; i++) {
    start = 0; // 设置二分查找的起始位置
    end = res.length - 1; // 设置二分查找的结束位置
    
    // 如果当前元素大于结果数组中的最后一个元素，直接将其添加到结果数组中
    if (res[end] < nums[i]) {
      res.push(nums[i]);
      continue;
    }
    
    // 使用二分查找找到当前元素在结果数组中的合适位置
    while (start < end) {
      mid = (start + end) >> 1; // 计算中间位置
      if (res[mid] < nums[i]) {
        start = mid + 1; // 如果中间元素小于当前元素，调整起始位置
      } else {
        end = mid; // 如果中间元素大于或等于当前元素，调整结束位置
      }
    }
    
    // 将当前元素替换到结果数组中的合适位置
    res[start] = nums[i];
  }
  
  // 返回结果数组的长度，即最长递增子序列的长度
  return res.length;
}