300. 最长递增子序列
300. 最长递增子序列
🟠 🔖 数组
二分查找
动态规划
🔗 力扣
LeetCode
题目
Given an integer array nums
, return the length of the longest strictly increasing _ subsequence_.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Follow up: Can you come up with an algorithm that runs in O(n log(n))
time complexity?
题目大意
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
进阶:
你能将算法的时间复杂度降低到 O(n logn)
吗?
解题思路
思路一:动态规划
可以使用动态规划来解决:
- 创建一个长度为
n
的数组dp
,其中dp[i]
表示以第i
个元素为结尾的最长递增子序列的长度。 - 初始化
dp
数组的所有元素为 1,因为每个元素自身也是一个长度为 1 的递增子序列。 - 对于每个位置
i
,遍历0
到i-1
的所有位置,如果nums[i] > nums[j]
,说明nums[i]
可以接在nums[j]
后面构成一个更长的递增子序列,更新dp[i] = Math.max(dp[i], dp[j] + 1)
。 - 最终,
dp
数组中的最大值即为所求的最长递增子序列的长度。
复杂度分析
- 时间复杂度:
O(n^2)
,其中n
是数组nums
的长度。主要的时间复杂度来自于两层嵌套的循环,外层循环遍历数组中的每个元素,而内层循环在每次外层循环中都遍历了之前的所有元素。 - 空间复杂度:
O(n)
,使用了一个长度为n
的数组来存储中间状态。
思路二:二分查找
使用二分查找优化最长递增子序列问题,主要利用了一个辅助数组 tails
。这个数组在遍历过程中,始终保持递增的状态。辅助数组 tails
的长度 len
表示当前已经找到的最长递增子序列的长度。二分查找的过程如下:
初始化左右指针:
- 初始时,
left
指向 0,right
指向len
。
- 初始时,
开始二分查找:
- 在当前的辅助数组
tails
中进行二分查找,找到第一个大于等于nums[i]
的位置。用mid
表示二分查找中间位置。 - 如果
tails[mid] < nums[i]
,说明当前的递增子序列可以继续延长,因此更新left = mid + 1
。 - 否则,说明当前递增子序列需要进行调整,因此更新
right = mid
。
- 在当前的辅助数组
更新辅助数组:
- 如果
left === len
,说明nums[i]
大于当前递增子序列的所有元素,将nums[i]
添加到辅助数组的末尾,并且递增子序列的长度len++
。 - 否则,将
nums[i]
替换掉辅助数组中第一个大于等于nums[i]
的元素。
- 如果
迭代下一个元素:
- 重复上述过程,直到遍历完整个数组
nums
。
- 重复上述过程,直到遍历完整个数组
最终结果:
- 辅助数组的长度
len
即为最长递增子序列的长度。
- 辅助数组的长度
举一个具体的示例来说明:
假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]
。
- 初始化时,辅助数组
tails
为空,len = 0
。 - 当处理元素
nums[0] = 10
时,tails
为空,将10
加入到tails
,len
变为1
。 - 当处理元素
nums[1] = 9
时,通过二分查找在tails
中找到第一个大于等于9
的位置,将tails[0]
替换为9
。 - 依此类推,处理完整个数组后,
tails
为[2, 3, 7, 18]
,len = 4
,最终结果为4
。
这种方法的核心在于通过二分查找,高效地维护了一个递增的辅助数组,从而在保证正确性的同时降低时间复杂度到 O(n logn)
。
复杂度分析
- 时间复杂度:
O(n logn)
,其中n
是数组nums
的长度。 - 空间复杂度:
O(len)
,其中len
是最长递增子序列的长度,使用了一个长度最长为len
的辅助数组。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
let dp = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; 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);
};
/**
* @param {number[]} nums
* @return {number}
*/
function lengthOfLIS(nums) {
if (!nums || nums.length === 0) {
return 0;
}
const n = nums.length;
const tails = [];
let len = 0;
for (let i = 0; i < n; i++) {
let left = 0;
let right = len;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
if (left === len) {
tails[len++] = nums[i];
} else {
tails[left] = nums[i];
}
}
return len;
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
334 | 递增的三元子序列 | [✓] | 贪心 数组 | 🟠 | 🀄️ 🔗 |
354 | 俄罗斯套娃信封问题 | [✓] | 数组 二分查找 动态规划 1+ | 🔴 | 🀄️ 🔗 |
646 | 最长数对链 | 贪心 数组 动态规划 1+ | 🟠 | 🀄️ 🔗 | |
673 | 最长递增子序列的个数 | 树状数组 线段树 数组 1+ | 🟠 | 🀄️ 🔗 | |
712 | 两个字符串的最小ASCII删除和 | [✓] | 字符串 动态规划 | 🟠 | 🀄️ 🔗 |
1671 | 得到山形数组的最少删除次数 | [✓] | 贪心 数组 二分查找 1+ | 🔴 | 🀄️ 🔗 |
1964 | 找出到每个位置为止最长的有效障碍赛跑路线 | 树状数组 数组 二分查找 | 🔴 | 🀄️ 🔗 | |
2111 | 使数组 K 递增的最少操作次数 | 数组 二分查找 | 🔴 | 🀄️ 🔗 | |
2355 | 你能拿走的最大图书数量 🔒 | 栈 数组 动态规划 1+ | 🔴 | 🀄️ 🔗 | |
2370 | 最长理想子序列 | 哈希表 字符串 动态规划 | 🟠 | 🀄️ 🔗 | |
2407 | 最长递增子序列 II | 树状数组 线段树 队列 4+ | 🔴 | 🀄️ 🔗 | |
3176 | 求出最长好子序列 I | 数组 哈希表 动态规划 | 🟠 | 🀄️ 🔗 | |
3177 | 求出最长好子序列 II | 数组 哈希表 动态规划 | 🔴 | 🀄️ 🔗 | |
3201 | 找出有效子序列的最大长度 I | 数组 动态规划 | 🟠 | 🀄️ 🔗 | |
3202 | 找出有效子序列的最大长度 II | 数组 动态规划 | 🟠 | 🀄️ 🔗 |