一、题目描述
给你一个整数数组 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)) 吗?
二、思路讲解
用dp[i] 表示以i 结尾的序列中,最大递增子序列的长度。那么我们在每个i 处,往前找比自己小的数字(记为j 处),将该处的dp值+1,即是i处的dp值(说明i处的数字可以接在j 处后面组成递增子序列)。dp数组中的最大值即为所求。
三、Java代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
//数组长度
int len = nums.length;
//最后结果
int res = 0;
//dp[i]表示以i结尾的序列的最大递增子序列长度
int []dp = new int[len];
//给dp赋初值
for(int i=0; i<len; i++) {
dp[i] = 1;
}
for(int i=0; i<len; i++) {
int big = 0;
for(int j=0; j<i; j++) {
if(nums[j]<nums[i]) {
big = Math.max(big, dp[j]);
}
}
dp[i] = big + 1;
res = Math.max(res, dp[i]);
}
return res;
}
}
时间复杂度: O(N^2)
空间复杂度: O(N)
四、算法优化
进阶要求是要时间复杂度为nlogn。我们的算法的时间复杂度主要为:遍历nums数组,使用n,无法优化;线性遍历[0, i-1) 求dp[i],使用n。我们可以考虑重新设计dp的思路。
设计一个tail数组,tail[i] 表示长度为i的递增序列的最小末尾数字。例如,4 5 1 9 8 5 序列中,长度为1的递增序列有4,5,1,9,8,5,所以tail[1]为1;长度为1的递增序列有4 5,4 9,4 8,
5 8, 5 9……所以tail[2] 为5;长度为3的递增序列有 4 5 9,4 5 8,所以tail[3] 为8。可以看出,tail为一个递增序列,在查找操作时,我们可以使用二分查找。
那么,我们在计算tail[i]的时候,只需要遍历nums,找到第一个比num大的tail[k],说明num更适合放在tail[k-1]位置,而不能接在tail[k]位置(接上就不递增了)。如果num比tail中所有数字都大,那就说明num适合接在所有递增序列之后,这时递增序列的长度又可以增加了。
参考:力扣300. 最长递增子序列(动态规划 + 二分查找,清晰图解)
class Solution {
public int lengthOfLIS(int[] nums) {
//数组长度
int len = nums.length;
//tail[i]表示,长度为i的递增序列的最小末尾数字
int []tail = new int[len];
//题目所求 递增序列的最大长度
int resLen = 0;
for(int i=0; i<len; i++) {
int left = 0;
int right = resLen;
//二分查找 找到比nums[i]大的tail,若找不到,说明nums[i]适合放在所有序列的末尾,那么就向后更新一个长度
while(left < right) {
int mid = (left+right) / 2;
if(tail[mid]<nums[i]) {
left = mid+1;
} else {
right = mid;
}
}
tail[left] = nums[i];
//更新长度
resLen = resLen==right? (resLen+1) : resLen;
}
return resLen;
}
}
时间复杂度: O(NlogN)文章来源:https://www.toymoban.com/news/detail-660819.html
空间复杂度: O(N)文章来源地址https://www.toymoban.com/news/detail-660819.html
到了这里,关于力扣300:最长递增子序列(Java动态规划+双指针)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!