链接: https://leetcode.cn/problems/russian-doll-envelopes/
题面
给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封。
解法
这道题目其实是最长递增子序列的一个变种,每次用大的套小的
如果直接以dp[i]表示以第i个信封为最后一个的最长序列长度,只能用N^2的时间复杂度完成
这个题就会用到之前提到过的一个套路
二维数据涉及排序,可以将第一关键字升序,第二关键字降序
这样可以保证以第二个维度找最长上升子序列的时候,第一维度一定是满足严格单调递增的
这个解法的关键在于,对于宽度 w 相同的数对,要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的,逆序排序保证在 w 相同的数对中最多只选取一个。
很巧妙的一个做法
代码
1 | class Solution { |
也可以单独对第二个维度进行处理,直接调用lower_bound
1 | class Solution { |
v1.5.2