C ++中的俄罗斯娃娃信封
假设我们有一些信封，这些信封的高度和宽度值成对出现。如果第二个信封的高度和宽度都小于第一个信封的高度和宽度，则可以将一个信封放入另一个信封中。因此，我们可以放入其他信封中的最大信封数是多少。因此，如果输入像[[5,5]，[6,4]，[6,8]，[2,3]]，则输出将为3，因为最小包络为[2,3]，然后是[5,5]，然后是[6,8]。
为了解决这个问题，我们将遵循以下步骤-
根据高度对数组v排序，当高度相同时，与宽度比较
如果v的大小等于0，则-
返回0
定义数组ret
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
ret[curr]：=temp[1]
在ret的末尾插入temp[1]
忽略以下部分，跳至下一个迭代
中：=低+（高-低）/2
如果ret[mid]<temp[1]，则-
除此以外
curr：=中+1
低：=中+1
高：=中-1
定义一个数组temp=v[i]
x：=temp[1]
低：=0，高：=ret大小，curr：=0
当低<=高时，执行-
如果curr<0，则-
如果curr>=ret的大小，则-
除此以外
ret的返回大小
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
if(a[0] == b[0])return a[1] > b[1];
return a[0] < b[0];
}
int maxEnvelopes(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
if(v.size() == 0)return 0;
vector <int> ret;
for(int i = 0; i < v.size(); i++){
vector <int> temp = v[i];
int x = temp[1];
int low = 0;
int high = ret.size() -1;
int curr = 0;
while(low <= high){
int mid = low + (high - low) / 2;
if(ret[mid]<temp[1]){
curr = mid + 1;
low = mid + 1;
}else{
high = mid - 1;
}
}
if(curr < 0) continue;
if(curr >= (int)ret.size()){
ret.push_back(temp[1]);;
}else{
ret[curr] = temp[1];
}
}
return ret.size();
}
};
main(){
Solution ob;
vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
cout << (ob.maxEnvelopes(v));
}输入项
{{5,5}, {6,4}, {6,8}, {2,3}}输出结果
3