354. 俄罗斯套娃信封问题
问题描述
给你一个二维整数数组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
提示：
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
思路：
这个题目是一个套娃问题，首先我们应该对数组进行排序，因为相同尺寸的信封不能够嵌套，所以我们按照每个子数组的第一个元素升序排序，第二个元素降序排序，这样这个问题就转化成了以第二个元素为主的最长上升子序列问题，这个思路好是好，但是想到前面快速排序需要耗费nlog2n，后面的那个动态规划又是n2级别，c++语言时间会超限
那么我们就使用二分查找的策略
我们从头开始遍历，如果f[i]是指到第i个元素为止的最长上升子序列的最后一个元素，
那么到最后我们求得的f数组一定是一个单调递增的数组，而且f数组里的元素个数不大于envelopes.size()
如果envelopes[i]/[1]大于我们的f[i-1],那么f[i]=envelopes[i]/[1];
我们遍历envelopes[i]/[1]如果比f[i-1]小, 就在f[i]中找到那个刚好比他大的元素然后把它替换掉
因为被替换掉的元素不会影响最大子序列长度的个数（不信就自己验证一下）
代码演示：
#include<iostream>#include<vector>#include<algorithm>//先把信封按照宽度进行升序排序，然后按照高度进行降序排序，//问题变成了在新的排好序的数组里寻找最长上升子序列using namespace std;class Solution {public:int maxEnvelopes_plus(vector<vector<int>>& envelopes){sort(envelopes.begin(),envelopes.end(),[](const auto s1,const auto s2){if(s1[0]!=s2[0])return s1[0]<s2[0];else return s1[1]>s2[1];});int n=envelopes.size();for(int i=0;i<envelopes.size();i++){for(int j=0;j<envelopes[i].size();j++){cout<<envelopes[i][j]<<" ";}cout<<endl;}cout<<"---------------------------------------------------"<<endl;vector<int>dp = {envelopes[0][1]};;int answer=1;for(int i=1;i<n;++i){cout<<"the"<<i<<endl;for(int i=0;i<dp.size();i++){cout<<dp[i]<<" ";}cout<<endl;int nums=envelopes[i][1];if(nums>dp.back()){dp.push_back(nums);}else{auto it=lower_bound(dp.begin(),dp.end(),nums);/*lower_bound()返回值是一个迭代器,返回指向大于等于nums的第一个值的位置*/cout<<"the location of the iteration is"<<*it<<endl;*it=nums;}}return dp.size();}};int main(){int shuzu[9][2]={{5,4},{6,4},{6,7},{2,3},{3,1},{5,3},{6,5},{7,2},{8,2}};vector<vector<int>>envelopes(9,vector<int>(2,1));for(int i=0;i<envelopes.size();i++){for(int j=0;j<envelopes[i].size();j++){envelopes[i][j]=shuzu[i][j];cout<<envelopes[i][j]<<" ";}cout<<endl;}cout<<"---------------------------------------------------"<<endl;Solution s;cout<<s.maxEnvelopes_plus(envelopes)<<endl;system("pause");return 0;}
