给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
注意:不允许旋转信封。
示例 1:
输入:envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出:3
解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2:
输入:envelopes = [[1,1],[1,1],[1,1]]
输出:1
本题和面试题 17.08. 马戏团人塔一样是最长递增子序列的二维模式
我们可以对第一维进度升序的排序,然后对第一维相等的数进行降序的排序,这样就可以不管第一维,直接进行第二维的最长递增子序列求解。
先看个例子,假如排序的结果是下面这样:
[[2, 3], [5, 4], [6, 5], [6, 7]]
如果我们只看第二个维度 [3, 4, 5, 7][3,4,5,7],会得出最长递增子序列的长度是 4 的结论。实际上,由于第 3 和第 4 个信封的第一个维度都是 6,导致他们不能套娃。所以,利用第一个维度递增,第二个维度递减的顺序排序,会得到下面的结果:
[[2, 3], [5, 4], [6, 7], [6, 5]]
这个时候,只看第二个维度 [3, 4, 7, 5][3,4,7,5],就会得到最长递增子序列的长度是 3 的正确结果。
主要有底下两种解法,一种是动态规划,还一种是贪心+二分
class Solution { public: // 动态规划 int bestSeqAtIndex(vector<int>& height, vector<int>& weight) { int num = height.size(); vector<vector<int>> temp(num); vector<int> dp(num,1); int maxnum = 1; for(int i = 0; i < num; i++){ temp[i] = {height[i],weight[i]}; } sort(temp.begin(),temp.end(),[](vector<int> &temp1, vector<int> &temp2){ return temp1[0] < temp2[0] || temp1[0] == temp2[0] && temp1[1] > temp2[1]; }); for(int i = 0; i < num; i++){ for(int j = 0; j < i; j++){ if(temp[j][1] < temp[i][1]){ dp[i] = max(dp[i],dp[j] + 1); maxnum = max(maxnum,dp[i]); } } } return maxnum; } };
class Solution { public: /* 先按宽从小到大排序,但是同一个宽度的按高度从大到小排序,然后高度就按最长子序列这种题型来做(贪心 + 二分)。 */ int maxEnvelopes(vector<vector<int>>& envelopes) { sort(envelopes.begin(),envelopes.end(),[](vector<int> &x1, vector<int> &x2){ return x1[0] < x2[0] || (x1[0] == x2[0] && x1[1] > x2[1]); }); int length = envelopes.size(); vector<int> tail; int maxnum = 1; tail.push_back(envelopes[0][1]); for(int i = 0; i < length; i++){ if(envelopes[i][1] > tail.back()){ tail.push_back(envelopes[i][1]); } else{ vector<int> ::iterator iter = lower_bound(tail.begin(),tail.end(),envelopes[i][1]); *iter = envelopes[i][1]; } } return tail.size(); } };
联系客服