还有星月可以寄望，还有宇宙可以浪漫不止。
参考300. 最长递增子序列。
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
- 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解题思路
经典题目，这里提供两种解法，上次做只会使用第一种动态规划方法，第二种使用单调递增队列（贪心）方法今天复习也能做出来了。
- 动态规划：转移公式dp[i] = max(dp[0..i-1]) + 1,dp[i]表示以nums[i]结尾的最长子序列
- 贪心：维护一个单调递增数组或队列L，对于各个num[i]，查找L中num[i]大于的第一个L[j],则把num[i]代替L[j+1],这样可以保证L长度要么变大或不变而不会变小。
dp O(n^2) 51ms
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 1) return 1;
//dp[i]表示以 nums[i]结尾的最长子序列(包含nums[i])长度
int[] dp = new int[nums.length];
dp[0] = 1;
int maxLen = 1;
for(int i = 1; i < nums.length; i ++) {
//元素相等可以跳过
if(nums[i] == nums[i -1]) dp[i] = dp[i-1];
else{
int maxPre = 0;
for(int j = 0; j < i; j ++) {
if(nums[j] < nums[i]){//只看小于num[i]的元素
//找到前面这些元素结尾的最大子序列长度
maxPre = Math.max(dp[j],maxPre);
}
}
dp[i] = maxPre + 1; //dp[i]即为最大值加一 因为dp[i]结尾最大
}
//记录最大值
maxLen = Math.max(maxLen,dp[i]);
}
return maxLen;
}
}
贪心 6ms
class Solution {
public int lengthOfLIS(int[] nums) {
//考虑使用单调递增队列 使用数组代替会更快2ms
List<Integer> res = new ArrayList<>();
for(int i = 0;i < nums.length; i++) {
//查找第一个大于res[i]的数，用nums代替 num[i]最大则加入队尾
int ri = findFirstNum(res,nums[i]);
if(ri >= res.size()) res.add(nums[i]);
else res.set(ri,nums[i]);
}
return res.size();
}
//枚举搜索
int findFirstNum(List<Integer> res,int num){
for(int i = res.size() - 1;i >= 0; i--){
//严格递增所以> 否则>=
if(num > res.get(i)) return i + 1;
}
return 0;
}
//res有序所以可用二分查找会更快 5ms
int findFirstNum2(List<Integer> res,int num){
int l = 0, r = res.size() - 1;
while (l <= r) {
int mid = l + (r - l)/2;//(l + r) >> 1;
if (num > res.get(mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
}
2023-03-22
