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