LeetCode 354 – Russian Doll Envelopes (俄罗斯套娃信封问题)

题目描述

给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi] 表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大时，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

解题思路

这个问题可以转化为一个最长递增子序列 (LIS) 的问题，但需要一些巧妙的处理：

1. 排序：首先对信封按照宽度 w 进行升序排序，如果宽度相同，则按照高度 h 降序排序。这样做的目的是确保在宽度相同的情况下，高度较大的信封不会被选入 LIS 中，避免出现宽度相同但高度不同的信封互相嵌套的情况。
2. 提取高度数组：将排序后的信封的高度提取出来，形成一个一维数组。问题就转化为了在这个高度数组中寻找最长递增子序列。
3. 动态规划求 LIS：可以使用动态规划或二分查找的方法来求解 LIS。动态规划的时间复杂度为 O(n^2)，而二分查找的时间复杂度为 O(n log n)。

代码实现 (二分查找)

def maxEnvelopes(envelopes):

envelopes.sort(key=lambda x: (x[0], -x[1]))

# 提取高度数组
heights = [h for _, h in envelopes]

# 二分查找求 LIS
def binary_search(tails, h):
    left, right = 0, len(tails)
    while left < right:
        mid = (left + right) // 2
        if tails[mid] < h:
            left = mid + 1
        else:
            right = mid
    return left

tails = []
for h in heights:
    idx = binary_search(tails, h)
    if idx == len(tails):
        tails.append(h)
    else:
        tails[idx] = h

return len(tails)

envelopes = [[5,4],[6,4],[6,7],[2,3]] print(maxEnvelopes(envelopes)) # 输出：3

解释

1. 排序：envelopes.sort(key=lambda x: (x[0], -x[1])) 将信封按宽度升序，高度降序排列。
2. 提取高度：heights = [h for _, h in envelopes] 提取排序后的信封高度。
3. 二分查找：binary_search 函数用于在 tails 数组中找到 h 应该插入的位置。
4. 构建 LIS：遍历 heights，使用二分查找更新 tails 数组，最终 tails 的长度即为 LIS 的长度。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是信封的数量。排序需要 O(n log n)，二分查找更新 LIS 需要 O(n log n)。
• 空间复杂度：O(n)，用于存储 heights 和 tails 数组。

总结

Russian Doll Envelopes 问题通过巧妙的排序和转化为 LIS 问题，可以使用高效的二分查找方法求解，是一个经典的动态规划与二分查找结合的例子。理解其核心思想对于解决类似的 LIS 问题很有帮助。