买拆车件上什么网站,做网站贵不贵,网站建设合同书保密条款,巢湖网站建设公司题目
300. 最长递增子序列
中等
相关标签
数组 二分查找 动态规划
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例…题目
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)) 吗?
思路和解题方法 if(nums.size()1) return nums.size();特判如果数组nums长度为0或1直接返回其长度。vectorint dp(nums.size(), 1);创建一个大小为nums长度的数组dp用于存储以nums[i]结尾的最长上升子序列的长度。初始值全部赋为1因为每个元素本身也可以构成一个长度为1的上升子序列。int ans 0;初始化最长上升子序列的长度为0。for(int i 1; i nums.size(); i)从第二个元素开始遍历数组nums。for(int j 0; j i; j)在i之前的元素中找到比nums[i]小的元素。if(nums[i] nums[j])如果nums[i]大于nums[j]则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中。dp[i] max(dp[i], dp[j] 1);更新以nums[i]结尾的最长上升子序列的长度。当前位置的值为前面比它小的元素中以每个元素结尾的最长上升子序列长度的最大值1。if(ans dp[i]) ans dp[i];更新最长上升子序列的长度。return ans;返回最长上升子序列的长度。 复杂度 时间复杂度: O(n*n) 时间复杂度分析 代码中使用了两重循环时间复杂度为O(n^2)。 其中内层循环每次迭代都会执行常数个操作比较和更新dp数组因此时间复杂度为O(1)。 外层循环的迭代次数为n-1因此时间复杂度为O(n)。 因此算法的总时间复杂度为O(n^2)。 空间复杂度 O(n) 空间复杂度分析 代码中使用了一个长度为n的dp数组因此空间复杂度为O(n)。 c 代码
class Solution {
public:int lengthOfLIS(vectorint nums) {if(nums.size()1) return nums.size();vectorint dp(nums.size(), 1); // 创建一个dp数组用于存储以nums[i]结尾的最长上升子序列的长度默认初始为1int ans 0; // 初始化最长上升子序列的长度为0for(int i 1; i nums.size(); i) // 遍历数组nums{for(int j 0; j i; j) // 在i之前的元素中找到比nums[i]小的元素{if(nums[i] nums[j]) // 如果nums[i]大于nums[j]则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中dp[i] max(dp[i], dp[j] 1); // 更新以nums[i]结尾的最长上升子序列的长度}if(ans dp[i]) // 更新最长上升子序列的长度ans dp[i];}return ans; // 返回最长上升子序列的长度}
}; Java代码
class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length]; // 创建一个大小为nums.length的数组dp用于存储以nums[i]结尾的最长上升子序列的长度默认初始为1int res 0; // 初始化最长上升子序列的长度为0Arrays.fill(dp, 1); // 将dp数组中的元素全部赋值为1for (int i 1; i dp.length; i) { // 遍历数组nums从第二个元素开始for (int j 0; j i; j) { // 在i之前的元素中找到比nums[i]小的元素if (nums[i] nums[j]) { // 如果nums[i]大于nums[j]则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中dp[i] Math.max(dp[i], dp[j] 1); // 更新以nums[i]结尾的最长上升子序列的长度}res Math.max(res, dp[i]); // 更新最长上升子序列的长度}}return res; // 返回最长上升子序列的长度}
}觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
