长大后想做什么?做回小孩!

0%

LeetCode——最长上升子序列

NO.65 最长上升子序列 中等

8QQPq1.png

刚看到题,我以为寻找的这个上升子序列需要是连续的递增元素,所以我想双指针。发现行不通,重新审题发现,示例中的子序列元素不是连续的。。。

思路一:动态规划

dp数组含义:dp[i]nums前i个元素中最长上升子序列的长度。

初始化:初始状态全部为1,因为每个元素自身至少是长度为1子序列。

状态转移:填写dp[i]时遍历j∈[0,i,

如果i元素>j元素则当前元素i可以接在j元素之后作为上升子序列dp[i]=Max(dp[i],dp[j]+1);

否则i元素<=j元素当前元素i不能拼接在j元素之后就忽略。

每次填写完dp[i]更新当前最长上升子序列长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLIS(int[] nums) {
if (nums==null||nums.length==0)return 0;
int[] dp=new int[nums.length];
int maxLen=0;
//初始化
Arrays.fill(dp,1);
//状态转移
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
//如果i元素>j元素,则i可以接在j元素后面作为上升子序列
if (nums[i]>nums[j])dp[i]=Math.max(dp[i],dp[j]+1);
}
//更新最大长度
maxLen=Math.max(maxLen,dp[i]);
}
return maxLen;
}

时间复杂度:O(n^2)

思路二:TreeSet

JAVA Api中的TreeSet有ceiling(x)方法,取大于x的数,如果不存在则返回null。(此方法时间复杂度O(logn),但是最坏情况下会退化到O(n))

按序遍历nums,到TreeSet中取大于num的数x,如果存在x则删除x并将num加入set,如果不存在就是所有的数都小于num就将num加入set。

最后返回set的大小即可。

1
2
3
4
5
6
7
8
9
10
11
12
public int lengthOfLIS(int[] nums) {
if (nums==null||nums.length==0)return 0;
TreeSet<Integer> set=new TreeSet<>();
for (int num : nums) {
Integer x = set.ceiling(num);
if (x != null) {
set.remove(x);
}
set.add(num);
}
return set.size();
}

最坏时间复杂度仍然是:O(n^2)


本人菜鸟,有错误请告知,感激不尽!

更多题解和学习记录博客:博客github