俄罗斯套娃信封问题

LIS最长递增子序列 - This article is part of a series.

Part : This Article

Part : 最长递增子序列

显然该问题是一个最长增子序列, 不过和

不同的是:1、本问题中的信封不一定要套前面那个信封. 2、本问题中的信封有2个纬度.

因此, 首先需要对信访进行排序,再套用

的模板.

首先对信封的宽度进行升序排序. 这样的话, 后面的信封的宽度一定大于等于前面的宽度. 然后再对高度进行降序排序. 这样当遇到一个和自己一样宽的信封, 那么这个信封的高度就会比自己高, 这个信封在g中的位置就会在自己后面.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        N = len(envelopes)
        envelopes.sort(key= lambda x : (x[0], -x[1]))
        g = [envelopes[0][1]]
        for w, h in envelopes:
            j = bisect_left(g, h) # 比较高度
            if j == len(g):
                g.append(h)
            else:
                g[j] = h
        
        return len(g)

LIS最长递增子序列 - This article is part of a series.

Part : This Article

Part : 最长递增子序列