跳至主要內容

俄罗斯套娃信封——二维LIS与贪心二分优化

老张2026/4/30大约 8 分钟

俄罗斯套娃信封——二维LIS与贪心二分优化

适读人群：Java后端工程师、DP+贪心综合学习者 | 阅读时长：约22分钟 | 难度：Hard

开篇故事

俄罗斯套娃信封是这20篇的压轴题，也是我觉得最能体现"算法思维精妙"的一道题。

问题本身不复杂：给你一堆信封，每个信封有宽度和高度，一个信封能套进另一个信封当且仅当两维均严格小于（不能相等）。问最多能套多少层？

直觉告诉我这是二维的LIS（最长递增子序列）。LIS本身有两种解法：O(n²)的DP和O(n log n)的贪心二分。那么二维LIS呢？

关键的转化在于排序策略：按宽度升序，宽度相同时按高度降序排列。这样做之后，同一宽度的信封就不能相互套叠（因为高度降序，无法形成严格递增的高度序列），整个问题就转化成一维的LIS——在高度数组上求LIS。

这个排序策略的设计，是这道题最精彩的地方。理解了为什么要"相同宽度时高度降序"，你就理解了这道Hard题的灵魂。

一、题目解析

题号：LeetCode 354. Russian Doll Envelopes

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

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组"俄罗斯套娃"信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例：

  • 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]，输出：3（[2,3] → [5,4] → [6,7]）

二、问题转化

2.1 二维LIS的挑战

直接在二维上做LIS，需要对每对信封判断是否可以套叠：宽度严格更大且高度也严格更大。这比一维LIS复杂，因为要同时满足两个维度的严格递增。

2.2 关键排序策略

按宽度升序，宽度相同时按高度降序。

排序后，对高度数组求LIS（严格递增），就等价于原题。

为什么这样排序有效？

当宽度相同时，两个信封不能相互套叠（宽度必须严格更大）。如果我们在宽度相同时按高度升序排列，那么在同宽度组内，可能出现高度递增的序列被LIS算法选中，导致选出了宽度相同的信封（违反约束）。

降序的妙处：宽度相同的信封，高度是降序排列，所以在宽度相同的那组里，高度数组是严格递减的。LIS只能从每组里选一个（因为选两个以上，其高度必然包含递减部分，不构成严格递增序列）。这样就自动排除了同宽度信封被同时选中的情况。

验证：

envelopes排序后（宽度升序，相同宽度高度降序）：

[[2,3], [5,4], [6,7], [6,4]]

高度数组：[3, 4, 7, 4]

LIS（严格递增）：[3, 4, 7]，长度=3。

[6,7]和[6,4]不会同时被选：因为高度数组里4在7之后，4<7不构成递增（4无法追加在7后面），所以最长是[3,4,7]或[3,4,4]（4不严格>4），答案是3。✓

三、解法一：排序 + O(n²) LIS

public class RussianDollEnvelopes {
    
    /**
     * 354. 俄罗斯套娃信封 - 排序 + O(n²) LIS
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n)
     */
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        
        // 排序：宽度升序，宽度相同时高度降序
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return b[1] - a[1];  // 宽度相同：高度降序！
        });
        
        // 在高度数组上求LIS
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

时间复杂度 O(n²)，在 n 较大时会超时（LeetCode 354 的数据范围 n 可达 100000）。

四、解法二：排序 + O(n log n) 贪心二分LIS

4.1 LIS的贪心二分思路

维护一个数组 tails，tails[i] 表示"长度为 i+1 的最长递增子序列中，末尾元素的最小值"。

对每个新元素 x：

  • 如果 x > tails 的最后一个元素：说明 x 可以追加到当前最长的LIS后面，tails.append(x)
  • 否则：在 tails 中找到第一个大于等于 x 的位置，用 x 替换它（"尝试用更小的值结尾，为后续扩展留更多空间"）

这里用的是二分查找，所以每个元素的处理是 O(log n)，总时间 O(n log n)。

/**
 * 354. 俄罗斯套娃信封 - 排序 + O(n log n) 贪心二分LIS
 * 时间复杂度：O(n log n)
 * 空间复杂度：O(n)
 */
public int maxEnvelopesOptimized(int[][] envelopes) {
    int n = envelopes.length;
    
    // 关键排序：宽度升序，宽度相同时高度降序
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];
        return b[1] - a[1];
    });
    
    // 提取高度数组，在其上求LIS
    int[] heights = new int[n];
    for (int i = 0; i < n; i++) heights[i] = envelopes[i][1];
    
    return lisLength(heights);
}

/**
 * 求严格递增的LIS长度（O(n log n)贪心二分）
 */
private int lisLength(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    
    for (int x : nums) {
        // 二分查找：在tails[0..size-1]中找第一个 >= x 的位置
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        // lo是插入位置：替换或追加
        tails[lo] = x;
        if (lo == size) size++;  // 追加到末尾，LIS长度+1
    }
    
    return size;
}

五、贪心二分LIS的正确性理解

5.1 tails 数组的含义

tails[i] = 目前为止，所有长度为 i+1 的LIS中，末尾元素的最小值。

关键性质：tails 数组始终是严格递增的。（可以用反证法证明：如果 tails[i] >= tails[i+1]，那么长度为 i+2 的LIS末尾元素不可能比长度为 i+1 的更大，矛盾。）

5.2 替换操作的意义

当 x 不能追加到末尾时，用 x 替换 tails 中第一个 >= x 的位置，这表示："存在一个长度为 lo+1 的LIS，其末尾可以更小（为x），这样未来有更多的数可以追加上来"。

这个操作不改变 tails 数组的长度（不影响已经找到的LIS长度），但为未来的扩展提供了更好的"候选末尾"。

Mermaid图解：

size=3，即LIS长度=3。✓

六、举一反三

LIS相关题目：

  1. LeetCode 300. 最长递增子序列：一维LIS，本题的基础
  2. LeetCode 673. 最长递增子序列的个数：LIS的计数版
  3. LeetCode 1671. 得到山形数组的最少删除次数：双向LIS

二维LIS通用思路：

  1. 排序第一维（升序），相同时第二维降序
  2. 在第二维上求LIS
  3. 利用降序消除同值情况对LIS的影响

七、踩坑实录

坑一：宽度相同时高度没有降序

这是最致命的错误。如果宽度相同时高度升序，同宽度的信封会被LIS算法同时选中（因为高度递增），导致答案偏大。必须是降序！

坑二：二分查找边界

求严格递增LIS时，二分查找找的是"第一个大于等于x"的位置（lower_bound），这样对于相等的值也会替换（等价于"不能相等"的严格递增）。如果改成"第一个严格大于x"（upper_bound），就变成了"可以相等的非递减序列"的LIS，两者行为不同。

坑三：tails数组的大小

tails 数组的实际有效长度是 size，而不是 tails.length。最后返回 size，不是 tails.length。

坑四：贪心LIS只在单调性成立时可用

贪心二分LIS的正确性依赖于"tails始终有序"的不变量。如果是一般的最优化子序列问题（非严格递增），需要检查是否满足这个性质，不能盲目套用。

八、总结与系列收尾

俄罗斯套娃信封综合了排序、LIS（DP和贪心）两大技术，是整个系列的完美压轴。

核心解题链：

  1. 认识到这是二维LIS问题
  2. 设计排序策略（宽度升序+相同宽度高度降序）将二维转化为一维
  3. 在高度数组上用 O(n log n) 的贪心二分求LIS
解法时间空间
排序 + O(n²) LISO(n² + n log n)O(n)
排序 + O(n log n) LISO(n log n)O(n)

系列总结

20篇 LeetCode 动态规划精讲到此全部完成。从爬楼梯（541）到俄罗斯套娃信封（560），我们覆盖了：

类型篇目
线性DP541、542、543、544、545、554、559
字符串DP546、547、548、550、551、552、553
区间DP548、549
树形DP542（337部分）
状态机DP554、555
二维DP546、547、550、551、553、556、557
LIS560

每一道题都不只是一道题，背后是一类问题的解法框架。把这20篇吃透，DP这条路就打通了大半。

继续努力，老张陪你一起。

编辑此页
最近更新:
贡献者: xiaozhangge