题解 | #信封嵌套问题#

题意：

给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B ，那么信封 A 可以放到信封 B 里，请求出信封最多可以嵌套多少层。

方法一:动态规划

如下方法二中的解题思路,不同之处是在于寻找dp中不小于letters[i][1]的最小值直接简单遍历寻找.

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param letters intvector<vector<>> 
   * @return int
   */
  //排序的比较函数，长越小排前面，长相同宽不同的宽越大排前面
  static bool cmp(vector<int>&a,vector<int>&b){
      if(a[0]==b[0]){
          return a[1]>b[1];
      }else{
          return a[0]<b[0];
      }
  }

  //寻找nums数组中比target大的最小值
  int search(vector<int> nums,int target){
      for(int i=0;i<nums.size();i++){
          if(nums[i]>target)
              return i;
      }
      return -1;
  }

  int maxLetters(vector<vector<int> >& letters) {
      // write code here
      int n=letters.size();
      if(n==0)
          return 0;
      //排序
      sort(letters.begin(),letters.end(),cmp);
      //动态数组dp存信封宽度
      vector<int> dp;
      dp.push_back(letters[0][1]);
      //遍历信封letters，更新数组dp
      for(int i=1;i<n;i++){
          int width=letters[i][1];
          if(width>dp.back())
              dp.push_back(width);
          //在数组dp中，找比width大的最小值，并将其替换为width。
          else{
              int index= search(dp,width);
              dp[index]=width;
          }
      }
      //dp的长度即为最终返回值
      return dp.size();
  }
};

复杂度分析：

时间复杂度： $O(n^{2})$ ，遍历数组lettes $O(n)$ , 寻找特定值 $O(n)$ ,总 $O(n^{2})$ 。
空间复杂度： $O(n)$ ，额外数组dp，其大小是信封最多嵌套的层数，当所有信封都能嵌套进去时取最大值n。

方法二：动态规划+二分法

解题思路：

本题目是题目————最长递增子序列的变式。

https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=196&&tqId=37129&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking
参考该题目的解法，同时由于题目要求时间复杂度O(nlogn)，空间复杂度O(n)，所以选择使用动态规划加二分法的方法来解决。
具体解题方法如下：

1.对二维数组letters排序，排序依照函数cmp的方法，按照长度递增，相同长度宽度递减的顺序。
2.分配动态数组dp，dp[i]---表示嵌套信封为i+1个时，最外层的信封的宽度的最小值。则数组dp的大小为最大嵌套信封个数，即为所求返回值。
3.遍历排序后的数组letters，按照如下方法更新数组dp。
（1）若letters[i][1]>dp.back()--->dp.push_back(letters[i][1]);
（2）若letters[i][1]<=dp.back()--->寻找dp中不小于letters[i][1]的最小值，寻找时使用二分法，如下函数dichotomy()所示，并将其更新为letters[i][1]。
4.遍历完毕，返回值dp.size()。

图解如下：

图片说明

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    //排序的比较函数，长越小排前面，长相同宽不同的宽越大排前面
    static bool cmp(vector<int>&a,vector<int>&b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        }else{
            return a[0]<b[0];
        }
    }

    //二分法寻找当前数组nums中比target大的最小值,或者跟target一样大的，返回索引。
    //其中数组nums严格递增，且nums中必定存在比target大或者与target一样大的
    int dichotomy(vector<int> nums,int target){
        int left=0,right=nums.size()-1;
        int cur;
        while(true){
            cur=left+(right-left)/2;
            if(nums[cur]<target){
                if(nums[cur+1]>target){
                    //nums[cur]<target<nums[cur+1] return cur+1
                    return cur+1;
                }
                else 
                    left=cur;
            }
            else if(nums[cur]>target){
                if(cur==0||nums[cur-1]<target)
                    //nums[0]>target or nums[cur-1]<target<nums[cur] return cur
                    return cur;
                else
                    right=cur;
            }
            else{
                return cur;
            }
        }
        return -1;
    }

    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int n=letters.size();
        if(n==0)
            return 0;
        //排序
        sort(letters.begin(),letters.end(),cmp);
        //动态数组dp存信封宽度
        vector<int> dp;
        dp.push_back(letters[0][1]);
        //遍历信封letters，更新数组dp
        for(int i=1;i<n;i++){
            int width=letters[i][1];
            if(width>dp.back())
                dp.push_back(width);
            //在数组dp中，找比width大的最小值，并将其替换为width。
            else{
                int index= dichotomy(dp,width);
                dp[index]=width;
            }
        }
        //dp的长度即为最终返回值
        return dp.size();
    }
};

复杂度分析：

时间复杂度： $O(nlogn)$ ，遍历数组lettes $O(n)$ , 在数组dp中利用二分法寻找特定值 $O(logn)$ ,总 $O(nlogn)$ 。
空间复杂度： $O(n)$ ，额外数组dp，其大小是信封最多嵌套的层数，当所有信封都能嵌套进去时取最大值n。