题目分析

题目的名字起得非常有意思哈，禁止套娃。这个题目在某厂的笔试题中遇到过，当时太菜了，没有想出来该如何求解，当时的题目是多米诺骨牌，前面的长和宽必须都小于后面的长和宽，问最长的多米多骨牌长度为多少。当初被虐，今天一定要学会它。

DP

这个题目搞清楚方法之后也非常简单，其实相当于一个二维的最长上升子序列问题，必须满足在两个维度上都上升。其实就是一个排序就可以解决。我们按照第一个维度的升序进行排列，这个小伙伴们都想得到，然后按照第二个维度的降序进行排列，再找第二个维度的最长上升子序列的长度即可。这个如何理解呢？

按照第一个维度升序排列后，后面元素的第一个维度一定大于等于前面的，而且按照第二个维度降序排列后，寻找最长上升子序列时，上升子序列后面的元素值一定大于前面的元素值，因此后面的元素的第一个维度一定大于前面的元素，不会出现等于的情况，如果等于，那么第二个维度降序排列，后面的元素值一定小于等于前面的元素值，上升子序列无法找到。

举一个例子，[3, 5], [5, 8], [5, 6], [5, 4], [6, 8]，按照第二个维度寻找[5, 8, 6, 4, 8]上升子序列的结果是[5, 6, 8]，[3, 5]的两个维度都严格小于[5, 6]，[5, 6]的两个维度都严格小于[6, 8]。也就是说第一个维度为5的元素，在[5, 6]后面时，其第二个维度一定小于6，如[5, 4]，那么寻找上升子序列时，要寻找大于6的元素，找不到4，所以保证上升子序列中的后面元素两个维度都一定大于前面的元素。

为什么给这道题目DP的标签呢，其实是最长上升子序列的DP求法

我们使用动态规划进行求解，dp[i]表示右端点选择第i个数可得的最长上升子序列，可以得到状态转移方程
$$dp[i] = \max_{j = 1}^{i - 1} dp[j] + 1 if nums[i] > nums[j]$$
当考虑到所有情况后，就可以得到右端点为任何情况下的最大值，然后求dp数组的最大值即可。DP的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。

class Solution:
    def maxEnvelopes(self, envelopes):
        def lis(nums):
            lens = len(nums)
            dp = [1] * lens 
            for i in range(1, lens):
                for j in range(i):
                    if nums[i] > nums[j]:
                        dp[i] = max(dp[i], dp[j] + 1)
            return max(dp) if lens else 0
        
        if not envelopes:
            return 0
        envelopes.sort(key=lambda x:(x[0], -x[1]))
        nums = [x[1] for x in envelopes]
        return lis(nums)

二分

和DP中的分析过程相同，只是在求最长上升子序列时采用二分的算法，降低时间复杂度。
我们思考一些可能出现的情况，假设前k个元素的最长上升子序列为[1, 3, 5, 7, 9]。

**如果第k + 1个元素大于9，假设为11，则最长上升子序列变为[1, 3, 5, 7, 9, 11]**。
如果第k + 1个元素小于9，假设为6，最长上升子序列长度不变，但是会将大于6的最小值变为6，则此时最长上升子序列变为[1, 3, 5, 6, 9]，当以后再出现7时，最长上升子序列的长度仍然不变，但是子序列就已经更新为更好的一组值了[1, 3, 5, 6, 7]。
也就是说当后续出现更小的值时，不会立刻改变最长子序列的长度，而是从中间的某个地方开始逐渐替换，当此时出现更大的数字时，仍然按照替换之前的子序列继续追加。如果此时出现较小的数字时，则继续替换。当替换到最后一个数字时，说明子序列已经出现了更优解，以后按照更优解进行计算。

从上升子序列中寻找大于某个值的最小值时，可以使用二分查找法，这样可以将第二次遍历的时间复杂度大大缩小。算法的时间复杂度为O(nlog(n))，空间复杂度为O(n)。

class Solution:
    def maxEnvelopes(self, envelopes):
        def lis(nums):
            res = []
            for x in nums:
                if not res or res[-1] < x:
                    res.append(x)
                else:
                    left, right = 0, len(res) - 1
                    while left < right:
                        mid = (left + right) // 2
                        if res[mid] < x:
                            left = mid + 1
                        else:
                            right = mid
                    res[left] = x
            return len(res)
        
        if not envelopes:
            return 0
        envelopes.sort(key=lambda x:(x[0], -x[1]))
        nums = [x[1] for x in envelopes]
        return lis(nums)

刷题总结

现在想想其实这个题目并不是非常困难，有时候只是一个排序的问题，就可以将一个中等难度的题目变成困难题目，小伙伴们要多做多练，这样遇到时才能够迅速反应过来。