Startup VO 面试真题解析：俄罗斯套娃信封问题（Maximum Number of Envelopes）

题目描述

给定一组信封 [width, height]，求最多能嵌套几层。信封 A 能装进信封 B 当且仅当 A 的宽和高都严格小于 B 的宽和高，不能旋转。

解题思路

按宽度升序排序；宽度相同时按高度降序，这样同一宽度的信封不会互相嵌套。排序后，问题退化为在高度序列上求最长严格递增子序列（LIS），用 patience sorting 的二分法做到 O(n log n)。

import bisect

def max_envelopes(envelopes):
    envs = sorted(envelopes, key=lambda x: (x[0], -x[1]))
    tails = []
    for _, h in envs:
        i = bisect.bisect_left(tails, h)
        if i == len(tails):
            tails.append(h)
        else:
            tails[i] = h
    return len(tails)

复杂度与易错点

排序 O(n log n)，LIS O(n log n)。宽度相同必须高度降序，否则同宽的两个信封会被错误计入嵌套；严格递增用 bisect_left 而非 bisect_right。

FAQ

为什么宽度相同时高度要降序排列？

若高度升序，同一宽度的信封可能组成递增序列被当成嵌套；高度降序保证同宽信封不可能构成严格递增的 LIS。

参考来源

• LeetCode 354 — Russian Doll Envelopes
• LeetCode 300 — Longest Increasing Subsequence

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。