题解 | #信封嵌套问题#

思路：

题目的主要信息：

• vector中是每个信封的长度和宽度，当一个信封长度和宽度都大于另一个信封时，便可以嵌套
• 题目要求最大嵌套数量，且长宽不能颠倒

方法一：动态规划
具体做法：
我们可以用动态规划来解决。首先对数组进行排序，将较长的信封放在前面，使之成为一个信封长度递减的序列。
维护一个辅助数组dp，表示仅使用信封下标为时的最大嵌套度。
我们遍历整个数组维护dp，对于，我们遍历其前面所有的信封，找到能放下它的最大嵌套度，并更新

class Solution {
public:
    int maxLetters(vector<vector<int> >& letters) {
        int n = letters.size();
        if(n == 0)
            return 0;
        // 优先按照长排序
        sort(letters.begin(), letters.end(), [](vector<int>& a, vector<int>& b){
            return a[0] > b[0];
        });
        vector<int> dp(n, 0); //dp[i]表示前面i个信封最多有多少嵌套
        int res = 0;
        for(int i = 0; i < n; i++){
            // 遍历该信封之前的信封，看能放下它的且最多层的个数
            int max = 0;
            for(int j = 0; j < i; j++){
                if(letters[j][0] > letters[i][0] && letters[j][1] > letters[i][1]){
                    if(max < dp[j]) // 如果可以放下当前信封，与当前最大比较
                        max = dp[j];
                }
            }
            dp[i] = max + 1;  // 遍历一圈，找到最高
            res = res > dp[i] ? res : dp[i]; // 维护答案
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，排序的复杂度为，两层遍历
• 空间复杂度：，辅助数组dp

方法二：动态规划改进（二分法）
具体做法：
我们首先还是要对数组进行排序，这次是让信封长度小的放前面，相同长度是宽度大的在前。既让长度是递增序列，我们只需要在后面找到宽度递增的信封依次嵌套即可。
维护一个辅助数组dp，其中表示前个元素可以组成的长度为j的最长严格递增子序列的末尾元素的最小值。在定义范围内，可以看出dp值是严格单调递增的，因为越长的子序列的末尾元素显然越大。
后面遍历原数组，对于宽度大于结尾宽度的，我们可以直接加入dp末尾，否则我们二分法（lower_bound函数）找到第一个大于等于当前宽度的位置，因为后面的元素都是长度递增，相同情况下宽度递减，所以我们更新更小的宽度到刚刚找的位置，这样才能嵌套更多，相当于每次都把最小的信封塞到了前面,因为相同长度下，选择了宽度更小的信封。

class Solution {
public:
    int maxLetters(vector<vector<int> >& letters) {
        int n = letters.size();
        if(n == 0)
            return 0;
        //按长度排序，不同于方法一，这次小的在前
        sort(letters.begin(), letters.end(), [](vector<int>& a, vector<int>& b){
            return a[0] < b[0];
        });
        vector<int> dp(1, letters[0][1]); //表示嵌套的信封
        int res = 0;
        for(int i = 1; i < n; i++){
            if(letters[i][1] > dp.back())
                dp.push_back(letters[i][1]); //宽度大于dp结尾，可以嵌套
            else{
                //二分查找找到第一个大于等于letters[i][1]的值
                auto iter = lower_bound(dp.begin(), dp.end(), letters[i][1]);
                *iter = letters[i][1];
            }
        }
        return dp.size();
    }
};

复杂度分析：

• 时间复杂度：，排序时间是，一次遍历，遍历中二分查找为
• 空间复杂度：，辅助数组dp