leetcode：354. 俄罗斯套娃信封问题

题目

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例：

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

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

解答 & 代码

本题是最长递增子序列问题的拓展：

将信封按宽度 w 升序、按高度 h 降序排序

如果不对高度 h 降序排序，只按宽度 w 升序排序，排序后的信封数组可能为 [(1,1),(1,2),(1,3),(1,4)]，这样对高度求最长递增子序列长度为 4，而实际上这些新封的宽度相等，因此无法套娃，正确答案应该是 1。
对高度 h 降序排序后，排序后的信封数组为 [(1,4),(1,3),(1,2),(1,1)]，这样对于同样的宽度，高度是递减的，同样宽度的高度不可能再组成长度大于 1 的递增序列，就避免了上述错误
另，注意： **cmp** 函数的参数必须传引用！！！否则后面求最长弟子序列即使用了二分法也会超时！！！

对高度数组求最长递增子序列的长度

求最长递增子序列

动态规划：超时

贪心法 + 二分

class Solution {
private:
// 注意：参数要传引用，否则会超时！！！！！！
static bool cmp(vector<int>& envelop1, vector<int>& envelop2)
{
  return envelop1[0] < envelop2[0] || 
          (envelop1[0] == envelop2[0] && envelop1[1] > envelop2[1]);
}
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
  // 1. 将信封按宽度 w 升序、按高度 h 降序排序
  sort(envelopes.begin(), envelopes.end(), cmp);
  int len = envelopes.size();

  // 2. 对高度数组求最长递增子序列的长度，就是本题的答案
  // 解法：贪心 + 二分
  // 设置数组 tails，tails[i] 代表长度为 i + 1 的上升子序列的末尾元素的最小值
  // 初始时 tails 数组长度 len = 1，tails[0] = nums[0] 
  vector<int> tails = {envelopes[0][1]};    
  for(int i = 1; i < len; ++i)
  {
      // 如果当前信封高度 > tails.back()，说明上升子序列的长度可以加一，
      // 将当前信封高度压入 tails 数组尾部，tails 数组的长度 len 加一
      if(envelopes[i][1] > tails.back())
          tails.push_back(envelopes[i][1]);
      // 否则，二分找到 tails[pos - 1] < 当前信封高度 < tails[pos] 的位置，
      // pos 就是 tails 数组中大于等于当前信封高度的左边界 leftBoundary
      // 用当前信封高度代替 tails[pos]
      else if(envelopes[i][1] < tails.back())
      {
          int target = envelopes[i][1];
          int left = 0;
          int right = tails.size() - 1;
          int leftBoundary = right;
          while(left <= right)
          {
              int mid = left + (right - left) / 2;
              if(tails[mid] >= target)
              {
                  leftBoundary = mid;
                  right = mid - 1;
              }
              else
                  left = mid + 1;
          }
          tails[leftBoundary] = target;
      }
  }
  // 返回 tails 数组的长度，就是最长递增子序列的长度
  return tails.size();
}
};

复杂度分析：设信封数为 N

时间复杂度 O(N logN)：排序的时间复杂度 O(N logN)，贪心 +二分查找的时间复杂度也是 O(N logN)
空间复杂度 O(N)：

执行结果：

执行结果：通过

执行用时：300 ms, 在所有 C++ 提交中击败了 55.22% 的用户
内存消耗：75.6 MB, 在所有 C++ 提交中击败了 57.67% 的用户

hot 100

[困难] 354. 俄罗斯套娃信封问题

题目

解答 & 代码