各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 39 天。今天力扣上的每日一题是「354. 俄罗斯套娃信封问题」。

解题思路

今天的题目要求信封套信封最多套多少层，并且套的过程中信封长与宽不能旋转；长或者宽相等的时候，两个信封不能套在一起。

可以抽象成：

  • 题意：找出二维数组的一个排列，使得其中有最长的单调递增子序列（两个维度都递增）。

我在之前的题解里面讲过：「遇事不决先排序」，排序能让数据变成有序的，降低了混乱程度，往往就能帮助我们理清思路。本题也是如此。

两个维度都递增的排序

第一感觉肯定是各种语言默认的排序方法：两个维度都递增的顺序。 对于题目给出的[[5,4],[6,4],[6,7],[2,3]]示例，如果按照两个维度都递增的排序方法，会得到：

  1. [[2, 3], [5, 4], [6, 4], [6, 7]]

然后我们利用最长递增子序列的方法，即使用动态规划，定义 $dp[i]$ 表示以 $i$ 结尾的最长递增子序列的长度。对每个 $i$ 的位置，遍历 $[0, i)$，对两个维度同时判断是否是严格递增（不可相等）的，如果是的话，$dp[i] = max(dp[i], dp[j] + 1)$。

这个方法对应的代码是：

  1. class Solution:
  2.     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
  3.         if not envelopes:
  4.             return 0
  5.         N = len(envelopes)
  6.         envelopes.sort()
  7.         res = 0
  8.         dp = [1] * N
  9.         for i in range(N):
  10.             for j in range(i):
  11.                 if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
  12.                     dp[i] = max(dp[i], dp[j] + 1)
  13.         return max(dp)
  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$O(N)$

该 Python 解法我在提交之后，会超时。其他语言有可能会通过。

第一维递增，第二维递减的排序

上面的方法，我们在循环中对两个维度都进行判断是否严格递增的。其实有个技巧，可以减少第一个维度的判断。

先看个例子，假如排序的结果是下面这样：

  1. [[2, 3], [5, 4], [6, 5], [6, 7]]

如果我们只看第二个维度 $[3, 4, 5, 7]$，会得出最长递增子序列的长度是 4 的结论。实际上，由于第 3 和第 4 个信封的第一个维度都是 6，导致他们不能套娃。所以，利用第一个维度递增，第二个维度递减的顺序排序，会得到下面的结果：

  1. [[2, 3], [5, 4], [6, 7], [6, 5]]

这个时候，只看第二个维度 $[3, 4, 7, 5]$，就会得到最长递增子序列的长度是 3 的正确结果。

该方法对应的代码为：

  1. class Solution:
  2.     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
  3.         if not envelopes:
  4.             return 0
  5.         N = len(envelopes)
  6.         envelopes.sort(key=lambda x: (x[0], -x[1]))
  7.         res = 0
  8.         dp = [1] * N
  9.         for i in range(N):
  10.             for j in range(i):
  11.                 if envelopes[j][1] < envelopes[i][1]:
  12.                     dp[i] = max(dp[i], dp[j] + 1)
  13.         return max(dp)å
  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$O(N)$

这个方法能通过，但是由于两重循环，导致效率较慢。

二分查找

TODO

刷题心得

本题是最长递增子序列拓展到二维。最好先去理解一下最长递增子序列。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！