LeetCode刷题笔记系列之一
题目链接：https://leetcode.com/problems/longest-increasing-subsequence/description/
题目描述：在给定未排序序列中找出最长的增长序列，只需返回长度
Example：
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
常规思路：
- 动态规划：
时间复杂度为O(n^2) 空间复杂度为O(n)
class Solution {
public int lengthOfLIS(int[] nums) {
int length = nums.length;
if(length == 0){
return 0;
}
int[] c = new int[length];
c[0] =1;
int max =1;
for(int i = 0;i<length;i++){
for(int j = i+1;j<length;j++){
if(i==0){
c[j] =1;
}
if(nums[i] <nums[j]){
c[j] = c[i] +1 > c[j] ? c[i] +1 : c[j];
if(c[j] > max){
max = c[j];
}
}
}
}
return max;
}
}
- 优化：
如何将时间复杂度优化为O(nlogn)
使用BinarySearch 进行优化 BinarySearch 的输入为已排序数组和指定的key，返回为
if key exists in array , return index
else return (-(insertion point)-1)
我们刚好可以利用 (-(insertion point)-1) 转换为 insertion point ，在遍历题目给定数组的同时，维护当前最长增长序列。这种方法同时可以得到最终的最长增长序列，而不只是长度。 代码如下：
import java.util.*;
class Solution {
public int lengthOfLIS(int[] nums) {
int length = nums.length;
if(length == 0){
return 0;
}
int[] c = new int[length];
int len = 0;//当前增长序列的长度
for(int num : nums){
int index = Arrays.binarySearch(c,0,len,num);
if(index < 0){
index = -(index+1);
}
c[index] = num;
if(index == len)
len++;
}
return len;
}
}
