题意整理
对于给定的输入序列,要从其中找到一个子序列,满足序列中的数字是单调上升的,在满足的子序列中找到长度最长的并进行输出。子序列是指一个数组删除若干元素,但不改变其他元素相对位置形成的序列。在有多个子序列满足的条件下,输出字典序最小的子序列。
例如:
输入:[1,2,8,6,4]
返回值:[1,2,4]
其最长递增子序列有3个,(1,2,8)、(1,2,6)、(1,2,4)其中第三个 按数值进行比较的字典序 最小,故答案为(1,2,4)
思路
- 先获得最长递增子序列的长度
- 根据长度逆序遍历输入序列,获得最长递增子序列
第一个想到的是暴力动态规划,但写出代码过后提交超时,一度不知道怎么优化,看了各路大佬的题解后才知道用二分进行优化,最终也成功自己实现了优化的动态规划代码。
解法一 暴力动态规划
首先定义dp数组:动态规划的dp数组存放以arr[i]结尾的递增子序列的个数。
获得dp数组后,逆序遍历一遍arr数组即可获得最长递增子序列。
base case: 初始时dp数组每个元素初始化为1,显然对每一个arr元素而言,它自身即为一个递增子序列。
递推关系: 对每一个,需要和前面所有元素
进行比较,若
且
(即
是以
结尾的最长递增子序列的成员)则
由递推关系很容易得知对于dp数组中值相同的元素,对应到arr数组中一定是在dp数组中相同值最后的元素最小对,容易看出
, 显然
,因此要获得字典序最小的最长递增子序列,只需逆序遍历一遍arr数组,选择第一个满足条件的元素进入结果序列即可。
运行提交会超时。
示例
给定输入: [2,1,5,3,6]
示例如下图:
代码
class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector the array * @return int整型vector */ vector<int> LIS(vector<int>& arr) { // write code here //第一步,先获得存放arr[i]结尾的递增子序列的个数的数组dp int length = arr.size(); vector<int> dp(length, 1); //dp数组存放arr[i]结尾的递增子序列的个数 int maxLen = 1; //记录最长子序列的长度 if (length == 1) return dp; for (int i = 0; i < length; i++){//计算dp[i] for (int j = 0; j < i; j++){// dp[i]初始为1,计算dp[i]时arr[i]与前面所有arr[j]进行比较,取最大 if (arr[j] < arr[i]) //若arr[j] < arr[i], 则arr[j]属于以arr[i]结尾的子序列 dp[i] = dp[j]+1 > dp[i] ? dp[j]+1 : dp[i]; } maxLen = maxLen>dp[i] ? maxLen : dp[i]; } //第二步,获得字典序最小的最长子序列,由dp的计算过程可知,若dp[i] == dp[j](i > j), 则arr[i] < arr[j] vector<int> res(maxLen); //最长子序列 for (int i = length; i >= 0; i--){ if (dp[i] == maxLen){ //从后往前遍历dp数组,第一个等于maxLen的下标进入最终子序列 res[--maxLen] = arr[i]; } } return res; } };
复杂度分析
时间复杂度:构建dp数组用了两层循环为,获得结果序列最大为
,总的时间复杂度为
空间复杂度:需要构建dp数组,空间复杂度为
解法二 动态规划+二分优化
维护一个tails数组,存放长度为i+1的递增子序列的最小的末尾元素。容易证明,tails一定是单调递增的序列,例如
,
一定是给定序列中最小的元素即
对应的长度为2的递增子序列,有
, 显然
, 同理
, 可知arr数组的最长递增子序列长度为3,值为
。由于tails数组单调递增,因此遍历arr数组时对
可以采用二分查找,找到满足
的位置,并将
插入该位置。由此所得tails数组的长度即为arr数组的最长递增子序列的长度。
由于要返回最长递增子序列,还需要维护一个相当于暴力动态规划中的辅助数组记录
的对应的最长递增子序列的长度。构建tails数组时,若
插入到tails末尾,即tails长度增加,则
, 若
插入tails中间位置,则
为tails被插入位置的下标+1(tails数组的下标表示子序列长度-1),最后逆序遍历
即可获得答案。
运行提交顺利通过。
示例
给定输入: [2,1,5,3,6]
示例如下图:
代码
class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector the array * @return int整型vector */ vector<int> LIS(vector<int>& arr) { // write code here //第一步,先获得tials数组,tails[i]存放长度为i+1的递增子序列的最小的末尾元素 int length = arr.size(); vector<int> tails(length, 0), dp(length,0); if (length <= 1) return arr; int size = 0; //tails当前长度 for (int i = 0; i < length; i++){//遍历一遍arr int low = 0, high = size; while (low != high){ //二分查找arr[i]应该替换或插入的位置 int mid = (low + high) / 2; if (arr[i] > tails[mid]) low = mid + 1; else high = mid; } tails[low] = arr[i]; //更新arr[i]到应该插入或替换的位置 if (low == size) {//若arr[i]插入到最后的位置,tails长度大小size++ size++; dp[i] = size; //记录当前下标对应最长递增子序列长度,该长度为当前size } else dp[i] = low + 1; //记录当前下标对应最长递增子序列长度,该长度为被替换的元素所对应的长度 } //第二步,获得字典序最小的最长子序列,由size得最长递增子序列的长度,且tails[size-1]存储了 //该子序列的末尾元素,因此只需倒序遍历找出以tials[size-1]结尾的递增子序列即可 vector<int> res(size); //最长子序列 for (int i = length - 1; i >= 0; i--){ if (dp[i] == size) //找到tail res[--size] = arr[i]; } return res; } };
复杂度分析
时间复杂度:构建tails数组,外层循环为,内层二分法为
,遍历dp数组最大为
,总的时间复杂度为
空间复杂度:需要两个辅助数组tails和dp,空间复杂度为