No.300 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列 。
示例 1:
text
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
text
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
text
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
进阶:
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
解题思路
实现
贪心 + 查找
- 贪心思路:如果要使上升子序列尽可能的长,则需要让序列上升得尽可能慢,因此希望每次在上升子序列最后加上的那个数尽可能的小。
- 算法流程:
- 当遍历的数字 > 记录最后一项末尾数字时,新增记录
- 否则,找到记录中第一个末尾大于该数字的记录(可用二分查找进行优化),更改其末尾
- 优化:由于都是通过操作末尾项,因此可以转换为一维数组来解决此问题
js
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
if (nums.length === 0) return 0
const tails = [nums[0]] // 原数组第 0 项
for (let i = 1; i < nums.length; i++) {
if (nums[i] > tails[tails.length - 1]) {
tails.push(nums[i])
} else {
// 这里的查找方式可以优化为二分查找
const index = tails.findIndex(x => x >= nums[i])
tails[index] = nums[i]
}
}
return tails.length
};
动态规划
- 确定 dp 数组及下标含义
dp[i] 表示 [0, i] 区间内以 nums[i] 结尾的最长递增子序列的长度
- 确定递推公式:dp[i] = Math.max(dp[i], dp[j] + 1)
如果 nums[i] > nums[j] 则说明当前元素复合递增子序列,则 dp[i] = Math.max(dp[i], dp[j] + 1)
如果 nums[i] < nums[j] 则说明当前元素不符合递增子序列,则什么都不做
- 如何初始化 dp 数组
每一个 i,对应的 dp[i] (即最长递增子序列)起始大小至少都是 1
- 确定遍历顺序
dp[i] 是有 [0, i-1] 各个位置的最长递增子序列推导而来,那么遍历 i 一定是从前向后遍历
- 举例推导 dp 数组
以 nums = [1, 3, 6, 7, 9, 4, 10, 5, 6] 为例:
- 复杂度
- 时间复杂度:O(n^2),遍历计算 dp 列表需 O(n),计算每个 dp[i] 需 O(n)
- 空间复杂度:O(n)
js
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
let n = nums.length;
if (n === 0) return 0;
let dp = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
};