导航：首页 > 互联网科技 >

golang刷leetcode技巧之如何实现最长上升子序列

发表于：2025-02-08 作者：千家信息网编辑

千家信息网最后更新 2025年02月08日，小编给大家分享一下golang刷leetcode技巧之如何实现最长上升子序列，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:

千家信息网最后更新 2025年02月08日golang刷leetcode技巧之如何实现最长上升子序列

小编给大家分享一下golang刷leetcode技巧之如何实现最长上升子序列，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路：

解法1:动态规划

1，用dp[i]标识，i 位置的最大长度

2，状态转移方程为 dp[i]=max(dp[j]+1) ,j>=0 j

3,取dp最大值

解法2:二分查找

1，用数组记录最长递增序列

2，如果当前元素比最大值大，则插在后面

2，通过二分查找在递增序列里查找位置

3，注意和普通二分查找的区别，如果但强位置比序列位置p的元素大，那么插入位置不是p而是p+1

4，输出p的长度

代码实现

func lengthOfLIS(nums []int) int {   if len(nums)<1{       return 0   }   dp:=make([]int,len(nums))    for i:=0;imax{           max=dp[i]       }   }   fmt.Println(dp)   return max}

func lengthOfLIS(nums []int) int {  if len(nums)<1{      return 0  }  var dp []int  dp=append(dp,nums[0])  for i:=1;idp[len(dp)-1]{          dp=append(dp,nums[i])      }else{          l:=0          r:=len(dp)-1          p:=0          for l<=r{              mid:=(l+r)>>1              if nums[i]>dp[mid]{                   p=mid+1                  l=mid+1              }else{                  r=mid-1              }          }           fmt.Println(dp,l,r,p,i,nums[i])           dp[p]=nums[i]            fmt.Println("111",dp,l,r,p,i,nums[i])      }  }  fmt.Println(dp)  return len(dp)}

看完了这篇文章，相信你对"golang刷leetcode技巧之如何实现最长上升子序列"有了一定的了解，如果想了解更多相关知识，欢迎关注行业资讯频道，感谢各位的阅读！

很赞哦！