[C++] LeetCode 354. ロシアの封筒問題

タイトル
幅と高さをマークした封筒がいくつか与えられ、幅と高さは整数対(w,h)で現れる.もう一つの封筒の幅と高さがこの封筒より大きい場合、この封筒はロシアの子供のように別の封筒に入れることができます.最大何個の封筒が1組の「ロシア套娃」封筒を構成できるかを計算してください(つまり、1つの封筒を別の封筒に入れることができます).
説明:封筒を回転させることはできません.
例:
入力:envelopes=[[5,4],[6,4],[6,7],[2,3]]出力:3解釈:最大封筒の個数は3で、組み合わせは:[2,3]=>[5,4]=>[6,7].
問題解
この問題は実際には最長の増分サブシーケンス問題に変換できる.wインクリメンタルソートの場合、hの場合、最も長いインクリメンタルサブシーケンスを見つけることです.最長増分子シーケンスの解法については、最長増分子シーケンスを参照してください.
メソッドの動的計画

class Solution {
public:
    int maxEnvelopes(vectorint, int>>& envelopes) {
        int n=envelopes.size(),res=1;
        if(n==0) return 0;
        sort(envelopes.begin(),envelopes.end());
        vector<int> vec(n,1);
        for(int i=1;iauto it=envelopes[i];
            for(int j=i-1;j>=0;j--){
                auto tmp=envelopes[j];
                if(it.first>tmp.first && it.second>tmp.second) vec[i]=max(vec[i],vec[j]+1);
                res=max(res,vec[i]);
            }
        }
        return res;
    }
};

メソッド2分検索
ここでは、envelopesがソートされる場合、wが等しい場合、hが減算ソートされる必要があることに注意してください.すなわち(4,5)と(4,6)は(4,6)、(4,5)であるべきである.

class Solution {
public:
    static bool cmp(pair<int,int> &a,pair<int,int>& b){
        if(a.first==b.first) return a.second>b.second;
        else return a.firstint maxEnvelopes(vectorint, int>>& envelopes) {
        int n=envelopes.size(),len=0;
        sort(envelopes.begin(),envelopes.end(),cmp);
        vector<int> vec(n,0);
        for(int i=0;iint m=envelopes[i].second;
            auto it=lower_bound(vec.begin(),vec.begin()+len,m);
            if(it==vec.begin()+len) vec[len++]=m;
            else *it=m;
        }
        return len;
    }
};

class Solution {
public:
    int maxEnvelopes(vectorint, int>>& envelopes) {
        int n=envelopes.size(),len=0;
        sort(envelopes.begin(),envelopes.end(),[](pair<int,int> &a,pair<int,int>& b){
            if(a.first==b.first) return a.second>b.second;
            else return a.firstvector<int> vec(n,0);
        for(int i=0;iint m=envelopes[i].second;
            auto it=lower_bound(vec.begin(),vec.begin()+len,m);
            if(it==vec.begin()+len) vec[len++]=m;
            else *it=m;
        }
        return len;
    }
};