俄罗斯套娃信封问题

354. 俄罗斯套娃信封问题

from functools import cmp_to_key
def mycmp(a, b):
    """
    自定义比较器。 先按第一个元素升序排序，第一个元素相同的，按照第二个元素降序排列。
    -1 代表保持不变
     1 代表交换顺序
    :param a:
    :param b:
    :return:
    """
    if a[0] == b[0]:
        if b[1] < a[1]:
            return -1
        else:
            return 1
    else:
        if a[0] < b[0]:
            return -1
        else:
            return 1
            

class Solution:
	"""
    354. 俄罗斯套娃信封问题
    https://leetcode.cn/problems/russian-doll-envelopes/
    """
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes_sort = sorted(envelopes, key=cmp_to_key(mycmp))
        height = [envelope[1] for envelope in envelopes_sort]

        res = self.lengthOfLIS(height)
        return res

    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        模拟蜘蛛纸牌
        :param nums:
        :return:
        """
        top = [0] * len(nums)
        #  牌堆数初始化为 0
        piles = 0
        for i in range(len(nums)):
            poker = nums[i]

            left, right = 0, piles
            while left < right:
                mid = left + (right - left) // 2
                if top[mid] > poker:
                    right = mid
                elif top[mid] < poker:
                    left = mid + 1
                else:
                    right = mid

            # 没找到合适的牌堆，新建⼀堆
            if left == piles:
                piles += 1
            # 把这张牌放到牌堆顶
            top[left] = poker

        return piles
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64