信封嵌套问题

问题描述：给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。
示例1
输入：[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]
返回值：4
说明：从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。
示例2
输入：[[1,4],[4,1]]
返回值：1

方法一

思路分析

     首先对所给的信封进行排序，我们需要按照信封的长度length进行升序排序，如果两个信封的长度相同则可以按照其宽度width进行降序排序，之后对宽度寻找最长递增序列，在寻找最长递增序列时使用动态规划的办法。这里需要解释为什么在长度相同的时候要按照其宽度进行降序排序，因为长度相同的信封无法进行嵌套，因此长度相同的信封只能选取一个，如果按照升序排序，那么就会造成无法嵌套但仍归纳为递增序列中造成错误。
动态规划构造最长自增序列的过程以及转移方程：
  • 设置$dp[i]$表示第i个位置上的最长递增序列长度，那么初始化所有位置$dp[i]=1$只有一个元素
  • 寻找$i$位置上的最长递增序列，需要寻找该位置之前左侧所有的元素，如果是递增的，那么$dp[i]=max(dp[i],dp[j]+1)$，其中$j<i$
  • 最后返回$dp$数组中的最大值即为最长递增序列的长度也即信封嵌套的层数

图解



C++核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0]) return a[1]>=b[1];//长度相同，宽度按照降序排序
        else return a[0]<b[0];//长度按照升序排序
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty()) return 0;
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//对数组元素排序
        vector<int > dp(n,0);//设置最长递增序列的数组
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)//从i位置之前的位置寻找可能的最长递增序列
            {
                if(letters[i][1]>=letters[j][1])
                {
                    dp[i]=max(dp[i],dp[j]+1);//动态规划的办法寻找每个位置的最长子序列数组
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
        
    }
};

复杂度分析

  • 时间复杂度：两层循环，循环次数为$1+2+3+4+n-1=n*(n-1)/2$，因此时间复杂度为$O(n^2)$
  • 空间复杂度：借助于一个辅助数组用于存放每个位置的最长递增序列长度，因此空间复杂度为$O(n)$

方法二

思路分析

      上面的方法时间复杂度高不符合规定的要求，为提高速度，采取以空间换时间的方式，使用二分法的办法优化动态规划，在求解$dp[i]$的过程中使用二分法的办法优化。先设置一个长度为n的数组ends，初始时ends[0]=letters[0][1]，其他位置上的值为0，$ends[b]=c$表示遍历到目前为止，在所有长度为b+1的递增序列中，最小的结尾数是c。每次ends数组存储当前位置之前所有长度为b+1的递增序列中，最小的结尾数是c的元素

图解



C++ 核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0]) return a[1]>=b[1];//长度相同，宽度按照降序排序
        else return a[0]<b[0];//长度按照升序排序
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty()) return 0;
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//对数组元素排序
        vector<int > dp(n,1);//设置最长递增序列的数组
        dp[0]=1;
        vector<int> ends(n);
        ends[0] = letters[0][1];//ends[b]=c，则表示遍历到目前为止，在所有长度为b+1的递增序列中，最小的结尾数是c
        int right = 0;
        int ll = 0;
        int rr = 0;
        int mm = 0;
        for (int i = 1; i < n; ++i) 
        {
            ll = 0;
            rr = right;
            while (ll <= rr) 
            {
                mm = (ll + rr) / 2;
                if (letters[i][1] > ends[mm]) 
                {
                    ll = mm + 1;
                } 
                else 
                {
                    rr = mm - 1;
                }
            }
            right = max(right, ll);
            ends[ll] = letters[i][1];
            dp[i] = ll + 1;
        }

        return *max_element(dp.begin(),dp.end());//返回最长递增序列的长度
        
    }
};

复杂度分析

  • 时间复杂度：循环遍历一次，每次查找为二分查找，因此时间复杂度为
  • 空间复杂度：借助于两个数组，因此空间复杂度为$O(n)$