LeetCode 第354题：俄罗斯套娃信封问题

📖 文章摘要

本文详细解析LeetCode第354题“俄罗斯套娃信封问题”，这是一道动态规划和二分查找的经典问题。文章提供了基于排序+二分查找和动态规划两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要深入理解动态规划和二分查找算法的读者。

核心知识点： 动态规划、二分查找、排序、最长递增子序列 难度等级： 困难 推荐人群： 具有一定算法基础，想要提升解题技巧的程序员

题目描述

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 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^5
• envelopes[i].length == 2
• 1 <= wi, hi <= 10^5

解题思路

本题可以使用两种主要解法：

解法一：排序 + 二分查找

1. 首先对信封按照宽度升序排序，当宽度相同时按高度降序排序
2. 排序后，问题转化为求高度数组的最长递增子序列
3. 使用二分查找优化最长递增子序列的查找过程

时间复杂度： O(nlogn)，其中n为信封数量 空间复杂度： O(n)

解法二：动态规划

1. 对信封按宽度升序排序
2. 使用dp数组记录以每个信封结尾的最大嵌套数量
3. 对每个信封，遍历前面的所有信封，更新dp值

时间复杂度： O(n^2) 空间复杂度： O(n)

代码实现

C# 实现

public class Solution {
    public int MaxEnvelopes(int[][] envelopes) {
        int n = envelopes.Length;
        // 按宽度升序排序，宽度相同时按高度降序排序
        Array.Sort(envelopes, (a, b) => {
            if (a[0] != b[0]) return a[0].CompareTo(b[0]);
            return b[1].CompareTo(a[1]);
        });
        
        // 使用二分查找求最长递增子序列
        List<int> dp = new List<int>();
        foreach (var envelope in envelopes) {
            int height = envelope[1];
            int index = dp.BinarySearch(height);
            if (index < 0) {
                index = ~index;
            }
            if (index == dp.Count) {
                dp.Add(height);
            } else {
                dp[index] = height;
            }
        }
        return dp.Count;
    }
}

Python 实现

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
            
        # 按宽度升序排序，宽度相同时按高度降序排序
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        
        # 使用二分查找求最长递增子序列
        dp = []
        for _, h in envelopes:
            i = bisect.bisect_left(dp, h)
            if i == len(dp):
                dp.append(h)
            else:
                dp[i] = h
        return len(dp)

C++ 实现

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) return 0;
        
        // 按宽度升序排序，宽度相同时按高度降序排序
        sort(envelopes.begin(), envelopes.end(), 
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
            });
        
        // 使用二分查找求最长递增子序列
        vector<int> dp;
        for (const auto& envelope : envelopes) {
            auto it = lower_bound(dp.begin(), dp.end(), envelope[1]);
            if (it == dp.end()) {
                dp.push_back(envelope[1]);
            } else {
                *it = envelope[1];
            }
        }
        return dp.size();
    }
};

执行结果

C# 实现

• 执行用时：264 ms
• 内存消耗：45.8 MB

Python 实现

• 执行用时：168 ms
• 内存消耗：17.2 MB

C++ 实现

• 执行用时：32 ms
• 内存消耗：16.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	32 ms	16.4 MB	执行效率最高，内存占用最小
Python	168 ms	17.2 MB	代码简洁，易于理解
C#	264 ms	45.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 巧妙利用排序将二维问题转化为一维问题
2. 💡 使用二分查找优化时间复杂度
3. 🔍 处理宽度相同时的特殊情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 忽略宽度相同时的排序处理
2. 🚫 使用普通动态规划导致超时
3. 🚫 未考虑空数组的边界情况
4. 🚫 二分查找实现不当导致错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
排序+二分查找	O(nlogn)	O(n)	效率高，适用于大规模数据	实现相对复杂
动态规划	O(n^2)	O(n)	思路直观，易于理解	效率较低，可能超时

相关题目

• LeetCode 300. 最长递增子序列 - 中等
• LeetCode 646. 最长数对链 - 中等
• LeetCode 674. 最长连续递增序列 - 简单

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第354题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！