今日任务
- [] 每日一题（LC-1187）
- [] LC-977 有序数组的平方
- [] LC-209 长度最小的子数组
- [] LC-59 螺旋数组II
每日一题LC-1187
LC-300
做每日一题前先做了一道LC-300, 因为LC-1187的题解说这道题可以用300的方法。
这道题DP不是最优解要n^2的时间复杂度，主要思想是DP记录以i元素结尾最长的严格递增子序列长度，这样遍历每个元素如果比之前的大就比较一下+1后和之前是不是最大的。最近很多这种题目啊，DP是检查以i为结尾的xxxx，可以整理一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxVal = dp[0];
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j <= i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxVal = Math.max(dp[i], maxVal);
}
return maxVal;
}
}
|
贪心做法，使用了O(n)的查找方式，如果用二分的话可以更加快
主要思路就是让ans数组中尽可能小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0)
return 0;
int[] ans = new int[nums.length + 1];
int len = 1;
ans[1] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > ans[len]) {
ans[++len] = nums[i];
} else {
int index = 0;
for (int j = len; j > 0; j--) {
if (ans[j] < nums[i]) {
index = j;
break;
}
}
ans[index + 1] = nums[i];
}
}
return len;
}
}
|
LC-1187 使数组严格递增
题目链接