Leetcode354俄罗斯套娃

俄罗斯套娃题题目

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明: 不允许旋转信封。

示例:

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

最长递增子序列题目

俄罗斯套娃信封是道困难题，其前置题目是300. 最长递增子序列，所以先以这个前置题目入手，其关键是知道状态转移方程。

问题描述： 给定一个无序的整数数组，找到其中最长上升子序列(LIS)的长度。

示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

最长递增子序列题解1

点击查看题解

问题的关键是状态转移方程为 : dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]。

需要注意的是这里的状态dp[j]指的是以第j个数字结尾的子序列(注意是子序列以num[i]结尾)的最长的长度。

根据状态转移方程，代码就出来了：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1] * len(nums) # 最小是1，也就是子串只包含自己
        res = 0
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

时间复杂度是$O(n^2)$, 空间复杂度是O(n). (有复杂度更低的解法，但是先回到俄罗斯套娃题)

俄罗斯套娃题题解1

找到同时满足envelopes[0]递增、envelopes[1]也递增的序列。

首先第一步是排序，将信封的envelopes[0]小到大排序, 比如有[6,7], [7,9], [8,8], [9,9].

由于envelopes[0]递增（这里先不考虑envelopes[0]相等的情况），只需要考虑envelopes[1]的最长递增子序列就可以了。

但是如果出现了envelopes[0]相等的情况，比如[9, 9], [1, 2], [1, 3], [1, 1], [1, 1]怎么处理呢。

其实很简单，就是再对envelopes[1]做降序处理，变成[9, 9], [1, 3], [1, 2], [1, 1], [1, 1]，也就是envelops[0]相等的时候，envelops[1]一定递减，使得后一个信封一定不会套住前一个信封，否则[1, 2], [1, 3]由于3大于2，将会算出[1, 3]信封套进[1, 2]。

现在来模拟对envelopes[1] ``[9，3，2，1(a)，1(b)]最长递增子序列过程:

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

时间复杂度是$O(n^2)$, 空间复杂度是O(n).

最长递增子序列题解2

点击查看题解

上面的题解链接有图解。这里的关键是dp[i]用来存放长度为i的子序列末尾的最小的数字。

e..g. [10, 9, 2, 5, 3, 7, 21, 18]

# Dynamic programming + Dichotomy.
class Solution:
    def lengthOfLIS(self, nums: [int]) -> int:
        tails, res = [0] * len(nums), 0
        for num in nums:
            i, j = 0, res
            while i < j:
                m = (i + j) // 2
                if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
                else: j = m
            tails[i] = num
            if j == res: res += 1
        return res

俄罗斯套娃题题解2

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        envelopes.sort(key=lambda x:(x[0], -x[1]))
        res = 0
        tails = [None] * len(envelopes)
        for x, y in envelopes:
            i, j = 0, res
            while i < j:
                mid = i + (j-i) // 2
                if tails[mid] < y:
                    i = mid + 1
                else:
                    j = mid
            tails[j] = y
            if j == res:
                res += 1
        return res