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
• -10^4 <= nums[i] <= 10^4

进阶：

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

解析

刷动归的第二天，又成功地被难倒了，知道 dp 该怎么定义，但不知道怎么由 dp[i-1] 推导出 dp[i]，完全没想到还可以再循环一遍前面的数组？虽然没犯规，但真没想到这操作...👻

• 动态规划O(n^2)

  • 难点就是怎么由 dp[i-1] 推出 dp[i]：找出nums[0...i-1]中所有小于nums[i]的记为nums[j]，然后比较这些nums[j]中对应的dp[j]+1的最大值，就是dp[i]的值。
  • 那为什么不用nums[i]前面所有比它小的数的个数再加上1呢？因为这些数的顺序不知道，不能保证这些数是单调递增的。

  /**
   * @param {number[]} nums
   * @return {number}
   */
  var lengthOfLIS = function(nums) {
    const len = nums.length;
    let max = 1;
    let dp = new Array(len).fill(1);// dp[i]表示nums[0...i]的最长递增子序列
    for(let i=1; i<len; i++) {
      for(let j=0; j<i; j++) {
        if(nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j]+1);
        }
      }
      if(dp[i] > max) max = dp[i];//max表示的是dp[i]中最大值，因为dp[len-1]不一定是最长递增子序列的长度
    }
    return max;
  };
  

• 动态规划 + 二分查找O(nlogn)

  • 设置一个一维数组inArr，数组是单调递增的，遍历nums
    • 如果nums[i]比inArr的最后一个值要大，则把nums[i]加入inArr最后面
    • 否则，用二分查找找到一个比它大的所有数中最小的进行替换（即保证inArr单调递增），inArr[j] = nums[i]，继续遍历
    • 需要注意的一点是，为什么只是进行替换，这样不是打乱了nums[i]在数组中的前后顺序吗？这个没有关系，因为最后的结果是数组inArr的长度，如果有新的更长的结果，会覆盖掉之前的结果。
  • 这个过程到底是哪里优化了呢？
  • 遍历nums的时间复杂度是O(n)，对于每一个nums[i]，需要二分查找inArr插入的位置，需要O(logn)，所以总的时间复杂度为O(nlogn)
  • 从动态规划的角度看，inArr[i]其实就是递增子序列长度为i中，值最小的那个，但是我觉得好像这个思想和动归没太大关系...

  这优化部分是看多位大佬的题解之后反推出来的🙊🙊，附一篇我认为比较易懂的题解贪心算法+二分法（用“砖头砌塔”来帮助理解） (opens new window)。

  // O(nlogn)优化，动态规划+二分查找
  const len = nums.length;
  let inArr = [-1e4-1,nums[0]];    
  for(let i=1; i<len; i++) {
    let inlen = inArr.length;
    let l = 0, r = inlen, pos = -1;
    while(l <= r) {
      let mid = Math.floor((l + r) / 2);
      if(inArr[mid] < nums[i]) {
        pos = mid;
        l = mid + 1; 
      } else {
        r = mid - 1;
      }
    }
    inArr[pos+1] = nums[i]; 
  }
  return inArr.length;