时隔很久的重新刷题，然后第一道就是一道hard，本着不服输的原则，我立马去看了，然后迅速打开了讲解，然后恍然大悟，立马开始敲代码，10分钟后，画面依然定格在它原来的样子。我用c++写的，但是对于c++的函数我其实并不知道什么。这道题的思路是先进行排序，然后转变成求最长上升子序列的问题。信封的嵌套规则是：if w1<w2&&h1<h2则信封1可以放进信封2。要求的是一个最大的嵌套数。
1.根据w进行一个降序排序，如果w相同则对h进行一个升序排序。n1[w1,h1],n2[w2,h2]
2.得到排序结束之后的一个二维数组,然后对h进行一个最长子序列的求解，得到的就是我们要的结果。
想法很美好，但是，这个排序怎么搞？我一开始居然打算手写排序，用快排，但是我觉得应该不至于,java都有自己的排序函数，c++怎么会没有呢？果然，只是我知识浅薄，然后就学习了一波c++的sort函数。
需要包含头文件：#
在这里我主要使用sort函数来对w进行升序排序，然后在w相同时对h进行降序排序，即对二维数组的一个二级排序。
sort(buffer,buffer+n,cmp)
其中
buffer:待排序数组起始地址
buffer+n: n就是待排序的元素数量，buffer+n就是待排序数组尾地址
cmp：指定排序的方式，取值为1/true:升序 0/false:降序，缺省表示升序。
用来处理我们的第一问：
1 bool cmp(vector<int>&v1,vector<int>&v2){ 2 if(v1[0]==v2[0]){//w相等 3 return v1[1]>v2[1]; 4 }else{//w不相等 5 return v[0]<v2[0]; 6 } 7 }
这个问题的整体代码：(代码是搬运了大佬的回答，感觉比较清晰，在leetcode的答题中复制的，所以不知道谁写的)
1 int maxEnvelopes(vector<vector<int>>& envelopes) { 2 sort(envelopes.begin(), envelopes.end(),cmp); 3 //利用LIS算法求出h的最长递增子序列 4 return lengthOfLIS(envelopes); 5 }
1 int lengthOfLIS(vector<vector<int>>& nums) { 2 int n = nums.size(); 3 if(n == 0) 4 return 0; 5 vector<int> dp(n + 1, 0);//dp[i]表示长度为i的上升序列的最小末尾元素 6 //末尾元素越小，那么它的后续发展潜力更大 7 //即在后面追加更大元素以形成更长上升序列的几率更大 8 int len = 1; 9 dp[len] = nums[0][1]; 10 for(int i = 1; i < n; i++){ 11 if(nums[i][1] > dp[len]){//大于末尾最小数字 加入即可 12 dp[++len] = nums[i][1]; 13 } 14 else{//nums[i] <= nums[i - 1] 15 int l = 1; 16 int r = len; 17 int pos = 0;//要是没有找到比它小的 说明都大于它 因此直接替换0 + 1处即可 18 //二分法在dp中找到比nums[i]小的第一个元素 19 while(l <= r){//细节 必须等于 20 int mid = (l + r) / 2;// /2 21 if(nums[i][1] > dp[mid]){ 22 pos = mid; 23 l = mid + 1; 24 } 25 else{ 26 r = mid - 1; 27 } 28 } 29 dp[pos + 1] = nums[i][1];//并将其替换 30 } 31 } 32 return len; 33 }