Menu Close

动态规划解最长子序列子串等一类问题之最长连续子序列[White-lipped Deer]

night-4790788_960_720.jpg

1.最长连续序列

1591142573977.png

方法1:Sort+Compare

  • 先排序,题意要求连续序列,即可以比较nums[i]nums[i - 1],如果不相等,表示是递增的趋势,相等则反之,递增后需要判断是否连续,即相邻的元素差值是否为1

  • 下面的代码处理边界case[-1,0],不会比较maxcur的值,需要在最后一道防线拦截一次

完整代码

复杂度分析

  • 时间复杂度:O(Nlog(N))N是数组的长度,排序的复杂度
  • 空间复杂度:O(1),常量级别的空间

方法2:Hash

  • 准备一个set,首先将所有的num装进set
  • for loop 数组,如果当前遍历到的元素num-1不在set中,说明这是一段新的可能出现的递增序列,变量curNum置为numwhile循环判断curNum+1是否在set中,是则表示是连续的
  • 记录max

复杂度分析

  • 时间复杂度:O(N),尽管在 for 循环中嵌套了一个 while 循环,时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 curNum 遇到了一个序列的开始, while 循环才会被执行(也就是 curNum-1 不在数组 nums 里), while 循环在整个运行过程中只会被迭代N次。这意味着尽管看起来时间复杂度为 O(N^2) , 实际这个嵌套循环只会运行 O(N+N)=O(N) 次。所有的计算都是线性时间的,所以总的时间复杂度是O(N)
  • 空间复杂度:O(1),常量级别的空间

2. 最长上升连续子序列

1591142393101.png

使用 O(n) 时间和 O(1) 额外空间来解决

  • O(1)的空间复杂度来处理,会比较麻烦,需要压缩空间,题意中的最长上升连续子序列,定义为从左到右和从右到左均可以
  • 准备两个数组,大小都为2
    • start记录从左到右的连续递增子序列的最长长度
    • end记录从右到做的连续递增子序列的最长长度

推荐阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1