What is the time complexity of the Russian Doll Envelopes problem?

The time complexity is O(n log n), where n is the number of envelopes, due to sorting and the binary search on the dynamic programming array.

How do we deal with envelopes having the same width in the Russian Doll Envelopes problem?

Envelopes with the same width should be sorted in descending order of height to ensure we don’t mistakenly include non-nested envelopes.

What dynamic programming approach is used in Russian Doll Envelopes?

The problem uses a dynamic programming approach where we maintain an array of minimum possible heights for increasing subsequences, and binary search helps efficiently update this array.

What is the binary search used for in the Russian Doll Envelopes problem?

Binary search is used to find the position in the dynamic programming array where the current envelope’s height can extend or replace an existing subsequence.

Can the solution to the Russian Doll Envelopes problem be optimized for space complexity?

Yes, the space complexity can be reduced by using a more compact data structure to track the subsequences, though the core time complexity will remain O(n log n).

#354

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [w i , h i ] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（…

数组二分查找动态规划排序

题目描述

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

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

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

注意：不允许旋转信封。

示例 1：

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

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

1 <= envelopes.length <= 10⁵
envelopes[i].length == 2
1 <= w_i, h_i <= 10⁵

lightbulb

解题思路

方法一：贪心 + 二分查找

时间复杂度 O(nlogn)。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for clear understanding of dynamic programming and binary search usage together.
question_mark
Assess the candidate's ability to explain how sorting impacts the overall approach.
question_mark
Check for familiarity with state transitions in dynamic programming problems.

warning

常见陷阱

外企场景

error
Failing to sort the envelopes correctly, especially handling ties in width by sorting in descending order of height.
error
Overcomplicating the problem by trying to use brute force to compare all pairs of envelopes.
error
Misunderstanding the role of binary search in the dynamic programming step, potentially leading to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if envelopes have more than two dimensions?
arrow_right_alt
What if the envelopes are in a randomized order with no restrictions?
arrow_right_alt
Can the approach be optimized further for lower space complexity?

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #1187 使数组严格递增 #1235 规划兼职工作