300. 最长上升子序列 + 354. 俄罗斯套娃信封问题

题目:

链接:https://leetcode-cn.com/problems/russian-doll-envelopes/

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

说明:
不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

 

解答:

这道题是最长递增子序列(LIS)的变形。

所以先看下最长递增子序列的解法:


 

题目:

链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解法:

子序列是指保持数组中原有顺序的不连续的元素序列,子串是额外满足连续性质的子序列。这两个的区别要搞清楚。

方法1:

如果前面一个元素的最长上升子序列长度为L,后面有个元素比该元素大,那就可以插到前面序列末尾。很显然要动态规划来计算。

建立dp数组,dp[i]表示截止到索引为i的元素,其最长上升子序列的长度。

对于每个索引i,遍历其前面0~i-1的所有元素j,如果有nums[j]<nums[i],那就可以把i插到j的子序列末尾。取所有j中子序列最长的那个。

代码:

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4         int n=nums.size();
 5         if(n==0){return 0;}
 6         vector<int> dp(n,0);
 7         vector<int> tail(n,0);
 8         dp[0]=1;
 9         int res=1;
10         for(int i=1;i<n;++i){
11             dp[i]=1;
12             int mx=i;
13             for(int j=0;j<i;++j){
14                 if(nums[i]>nums[j] and dp[j]>=dp[mx]){
15                     mx=j;
16                 }
17             }
18             dp[i]+=mx!=i?dp[mx]:0;
19             res=max(res,dp[i]);
20         }22         return res;
23     }
24 };

该算法时间为O(n^2),因为两个for循环。

进阶的nlogn方法:

保存一个数组,存储当前的最长子序列。

之后每遇到一个元素nums[i],如果大于序列尾部,那直接放到序列尾部。

如果小于等于尾部,那么利用二分法查找nums[i]应该插入的位置,并插入。

如之前有2,4,6,9序列,现在遍历到元素5。那我们把6替换为5,新序列为2,4,5,9。

简单解释一下:这里是利用贪心,即越小的尾部元素,后面能构成更长的最长子序列的可能性就越大。比如2,4,5和2,4,6,我们显然要取2,4,5。这样可能后面有个元素6,就可以构成2,4,5,6。

所以严格来说,数组中存储的并不是严格的到目前为止的LIS,但长度确实是我们目前能找到的最长连续子序列长度。

或者你还可以这么考虑:

数组第i位存的的长度为i+1的最长子序列的最小末尾元素。

比如原始数组为:10,9,2,5,3,7,101,18,4,8,6,12。

我们递推一遍我们的结果数组:

10

9             因为9比10小,替换了10

2      2替换9

2,5    5比2大,可以构成长度为2的LIS

2,3    3比5小,替换了5。或者也可以理解为长度为2的LIS的末尾元素是3

2,3,7    7比3大,构成长度为3的LIS

2,3,7,101  101比7大,构成长度为4的LIS

2,3,7,18  18替换101

2,3,4,18  4替换7

2,3,4,8

2,3,4,6

2,3,4,6,12

所以还是这样理解这个数组吧:第i位存储长度为i+1的LIS的最小末尾元素。

下面代码中利用了lower_bound函数,自己写二分法也可以。

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) 
 4     {
 5         vector<int> res;
 6         for(auto& num:nums)
 7         {
 8             if(res.empty() or res.back()<num)
 9             {
10                 res.push_back(num);
11             }
12             else{
13                 *lower_bound(res.begin(),res.end(),num)=num;
14             }
15         }
16         return res.size();
17     }
18 };

 


 

下面回到354题,

先按宽度排序,这样至少可以保证排在前面的不可能可以套在后面的外面。然后就调用LIS的方法1。

按照LIS的方法1:

 1 class Solution {
 2 public:
 3     int maxEnvelopes(vector<vector<int>>& envelopes) {
 4         int n=envelopes.size();
 5         if(n==0)
 6             return 0;
 7         sort(envelopes.begin(),envelopes.end(),[](vector<int>& a,vector<int>& b){
 8             return a[0]<b[0];
 9         });
10         vector<int> dp(n,1);
11         int res=1;
12         for(int i=1;i<n;++i){
13             int mx=i;
14             for(int j=0;j<i;++j){
15                 if(envelopes[j][0]<envelopes[i][0] and envelopes[j][1]<envelopes[i][1]){
16                     mx=dp[j]>=dp[mx]?j:mx;
17                 }
18             }
19             dp[i]+=mx!=i?dp[mx]:0;
20             res=max(res,dp[i]);
21         }
22         return res;
23     }
24 };

 

300. 最长上升子序列  + 354. 俄罗斯套娃信封问题

 

 

 

 按照LIS的方法2:

这种方法必须数组是有序的。但我们目前只有宽度有序,高度无序怎么办。

因为我们题目要求是宽高都大一号才能套娃,宽满足大一号的条件,但是高相等也是套不了娃的。

每个具体宽值的所有娃娃中,我们最多取一个。如:(1,2),(1,3),(1,4),宽都为1,但我们最多取其中一个。

所以考虑在宽度小到大排序的基础上,将高度大到小排序。并且我们的数组vec只保存高度。

即vec[i]指示的是:套了i+1层的娃娃中,可以套娃的最小高度。

比如初始数据  envelopes = [[5,4],[6,4],[6,7],[2,3]]

先排序为【2,3】【5,4】【6,4】【6,7】

递推一下vec:

3    表示目前套了一层娃娃,最小高度为3

3,4    目前套了两层娃娃,高度分别是3,4

3,4    由于【6,4】的4不大于数组末尾,所以套不了娃

3,4,7  可以套三层娃娃

 

最终选取的娃娃依次为:(1,2),(2,3),(3,4),(4,7),这恰好是我们想要的结果。 

 1 class Solution {
 2 public:
 3     int maxEnvelopes(vector<vector<int>>& envelopes) {
 4         if(envelopes.size()==0)
 5             return 0;
 6         sort(envelopes.begin(),envelopes.end(),[](vector<int>& a,vector<int>& b){
 7             return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];
 8         });
 9         //将宽度升序排序,宽度一样的,高度降序排序
10         //也可以高度升序排序,高度一样的,宽度降序排序
11         vector<int>vec;
12         for(auto &num:envelopes){
13             if(vec.empty() or num[1]>vec.back())
14             //num[1]>vec.back()说明遍历到了下一个宽值了,因为同一宽值的娃娃高度是递减的
15                 vec.push_back(num[1]);
16             else *lower_bound(vec.begin(), vec.end(), num[1])=num[1]; 
17         }
18         return vec.size();
19     }
20 };

300. 最长上升子序列  + 354. 俄罗斯套娃信封问题

 

上一篇:1、线性DP 354. 俄罗斯套娃信封问题


下一篇:Ubuntu12 国内源