那些过去，从未过去。
题目
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
输入描述
输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr(1≤arri≤1e9)。
输出描述
输出一行。代表你求出的最长的递增子序列。
样例1:
[输入]
9
2 1 5 3 6 4 8 9 7
[输出]
1 3 4 8 9
[说明]
样例2:
[输入]
5
1 2 8 6 4
[输出]
1 2 4
[说明]
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
解题思路
看到这道题目，有种似曾相识的感觉，仔细一看才发现不是这回事。LeetCode上的最长递增子序列是输出序列长度，属于中等medium题，而本题在此基础上需要输出序列且需要保证字典序最小，难度瞬间陡升。一开始的思路就是动态规划，确实思路没错，但是到输出队列且字典序最小时，卡点了。目前的研究是先分成两步解决：
1.通过dp动态规划求出最小序列长度。
2.生成最小字典序的序列，有两种思路，直观地找到所有的最长递增子序列，选择其中字典序最小的；或者使用某种贪心的思路找到字典序最小的序列。
第一步动态规划，首先需要定义好dp。
1.定义：设dp[i]表示以arr[i]结尾的最长递增子序列，此时注意，每一个dp值并不是递增的，比如第一个样例1，2 1 5 3 6 4 8 9 7，输出1 3 4 8 9，以9结尾的比以7结尾的序列长度更长。
2.寻找子问题推导：对于所有可与arr[i]组成上升序列的子序列上一个元素假设为arr[x]，x < i，需要满足条件：arr[x] < arr[i]（严格递增），即需要枚举序列，对所有满足arr[x] < arr[i]的元素选择一个最大的dp[x]，转移方程：
dp[i] = max(dp[x]) + 1, x < i且 arr[x] < arr[i]。
3.第一步代码如下：
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]即为最大值加一
}
//记录中间最大值记录，后面可能会有更长的序列所以继续遍历
maxLen = Math.max(maxLen,dp[i]);
}
return maxLen;
}
时间复杂度O(n^2)，双重循环遍历，可能会超时。
另一种O(nlogn)的思路，看见logn确实是二分：假如给出序列 mylist=[1， 3， 5， 6， 7， 2， 5， 7， 9， 10]，找最长序列的时候，看到1, 3, 5, 6, 7递增，长度len1=5，可能这个就是目标序列，记为答案一。 但是遇到2(mylist[5])时，有没有可能从1, 2, ... (mylist[0], mylist[5]...)会找到一个新的子序列， 且比之前找的序列1, 3, 5, 6, 7更长？记为答案二。验证答案二，看2以后的数字是否能找到新的递增序列。有两种结果，新的答案比第一次的答案短， 保留答案一； 新的答案比第一次的答案长， 用新的答案。 所以记录 1）新的答案上一个数字，继续往下找 2）若遍历结束了新的答案不够长，保留答案一。使用一个队列，每次更新最长子序列时，把子序列末尾最大值也就是arr[i]，替换队列中第一个大于arr[i]的位置，若没找到则直接放在队尾，队列的长度即为LIS。
解释：当找到2时，原来的[1, 3, 5, 6, 7], 3已经不在新的答案序列了，把3替换为2，依次进行，如果新的答案比第一次答案长， 整个序列被替换，如果没有第一个长，替换的次数不够，原来方案一里最大的数字还在末尾， 原始队列的长度不会被替换，那么始终能用队列的长度表示最长递增子序列。代码如下：
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;//最开始tails里面没有保存数所以为0
for(int num : nums) {
int i = 0, j = len-1; // 对tails进行二分查找 闭区间查找，注意j从len-1开始
int idx = lowerBound(tails,num,i,j);//左边找大于等于num的第一个数
tails[idx] = num;// 使用num替换查找到的i位置
if(len == idx) len++; // idx=len说明放在tails后面了len++
}
return len; // len即为LIS
}
//左闭右闭区间返回的是不变量l或r-1，表示>=target的左边第一个数
int lowerBound(int[] arr,int target, int l, int r) {
while(l <= r) {
int mid = l + (r-l)/2;
if(arr[mid] < target) l = mid+1;
else r = mid-1;
}
return l;
}
}
对二分不熟悉的小伙伴可以多学习巩固一下相关的写法，不管开区间闭区间写法还是小于等于或大于等条件，都是一样的思路，比如找大于x的第一个位置相当于找大于等于x+1的位置（对于整数区间），我个人习惯用闭区间。
第二步 求解字典序最小，需要利用到dp[i]记录的以nums[i]结尾的LIS：
// 反向遍历，每次都减少递增序列长度
int[] res = new int[len];
for (int i = n - 1; i >= 0; i--) {
//从后向前依次给子序列赋值
if (dp[i] == len) {//可能有多个dp[i]都是最长递增子序列 为何选择后面这个？
res[len - 1] = nums[i];
len -= 1;
}
}
return res;
倒序遍历时，可能有多个dp[i]都是最长递增子序列 为何选择后面这个？
反证：假设有dp[x] = dp[x+k] = maxLen，若nums[x] < nums[x+k]，则nums[x+k]可以接在nums[x]后面组成上升序列，则dp[x+k] > dp[x]矛盾。
最终代码如下：
class Solution {
public int[] LIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int[] dp = new int[n];
int len = 0;
for (int i = 0; i < n; i++) {
int l = 0, r = len - 1; // 对tails进行二分查找 闭区间查找，注意j从len-1开始
int idx = lowerBound(tails, nums[i], l, r);//左边找大于等于num的第一个数
tails[idx] = nums[i];// 使用num替换查找到的i位置
if (len == idx) len++; // idx=len说明放在tails后面了len++
dp[i] = idx + 1;
}
int[] res = new int[len];
for (int i = n - 1; i >= 0; i--) {
if (dp[i] == len) {
res[len - 1] = nums[i];
len -= 1;
}
}
return res;
}
//左闭右闭区间返回的是不变量l或r-1，表示>=target的左边第一个数
int lowerBound(int[] arr, int target, int l, int r) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] < target) l = mid + 1;
else r = mid - 1;
}
return l;// 没找到时，一直往右逼近，最终返回的是数组长度（r-l+1）
}
}
思考：打印所有最长递增子序列。
2024-03-29
网友评论