354. Russian Doll Envelopes

LIS 二分 贪心

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

• 1 <= envelopes.length <= 105

• envelopes[i].length == 2

• 1 <= wi, hi <= 105

分析：

主流高效解法：排序 + 二分查找 + 最长递增子序列（LIS）

核心思路：

• 先将信封按宽度升序排序，宽度相同时按高度降序排序。

• 然后只在高度上寻找最长递增子序列（LIS），用二分查找优化，时间复杂度 O(nlog⁡n)

宽度相同时按高度降序排序可以保证同宽度只取最小高度，满足贪心。

LIS主要是贪心算法，每次都选最小的数，为后面留空间。

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0],-x[1]))
        heights = [h for _, h in envelopes]
        #LIS
        res = []
        for h in heights:
            idx = bisect.bisect_left(res, h)
            if idx == len(res):
                res.append(h)
            else:
                res[idx] = h
        return len(res)