Leetcode354俄罗斯套娃

草祭收录于算法

2021-03-04 约 1466 字预计阅读 3 分钟

俄罗斯套娃题题目

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (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]结尾)的最长的长度。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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)]最长递增子序列过程:

dp[0]	9	1
dp[1]	9, 3	2
dp[2]	9, 2	2
dp[3]	9, 1(a)	2
dp[4]	9, 1(a) `因为envelopes[4][1] > envelops[3][1]不成立`	2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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