LeetCode 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。
示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

思路分析：首先我们将信封集按照宽度为主，高度为辅的升序排序。然后进行动态规划。（时间复杂度O(n² + n log₂n)，时间复杂度O(n)）

class Solution {
public:
    //按照宽为主次序，高为辅次序
    static bool myCmp(pair<int, int> &one, pair<int, int> &two){
        if (one.first == two.first){
            return one.second <= two.second;
        }
        else{
            return one.first <= two.first;
        }
    }
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int result = 1;
        int envelopesSize = envelopes.size();
        if (envelopesSize == 0){
            return 0;
        }
        vector<int> dp(envelopesSize, 1);//dp[i]表示第i个信封能套的信封个数（包括自己）
        sort(envelopes.begin(), envelopes.end(), myCmp);//按照宽为主次序，高为辅次序,升序排序
        //开始动态规划
        for (int beginIndex = 1; beginIndex < envelopesSize; ++beginIndex){
            for (int scanIndex = 0; scanIndex < beginIndex; ++scanIndex){
                if(envelopes[scanIndex].first < envelopes[beginIndex].first && envelopes[scanIndex].second < envelopes[beginIndex].second){
                    //动态转移方程
                    dp[beginIndex] = max(dp[beginIndex], dp[scanIndex] + 1);
                }
            }
            result = max(result, dp[beginIndex]);
        }
        return result;
    }
};

虽说是通过了，但是时间复杂度非常高。
方法二：将信封集按照宽度递增，高度递减进行排序，然后寻找高度最长递增子序列，即为结果。（时间复杂度O(n log₂n)，时间复杂度O(n)）
请先翻阅 LeetCode 最长上升子序列（动态规划、二分法）
里面介绍如何在O(nlog₂n)时间复杂度实现寻找最长递增子序列。

class Solution {
public:
    //按照宽为主次序，高为辅次序
    static bool myCmp(pair<int, int> &one, pair<int, int> &two){
        if (one.first == two.first){
            return one.second > two.second;
        }
        else{
            return one.first < two.first;
        }
    }
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int envelopesSize = envelopes.size();
        if (envelopesSize < 2){
            return envelopesSize;
        }
        sort(envelopes.begin(), envelopes.end(), myCmp);//按照宽为主次序，高为辅次序(宽递增，高递减排序
        //下面寻找最长递增子序列
        vector<int> enp;//用于寻找最长递增子序列
        for (int i = 0; i < envelopesSize; ++i){
            auto it = lower_bound(enp.begin(), enp.end(), envelopes[i].second);//在enp中寻找比envelopes[i].second大的迭代器
            if (it == enp.end()){
                enp.push_back(envelopes[i].second);
            }
            else{
                *it = envelopes[i].second;
            }
        }
        return enp.size();
    }
};