关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode354：俄罗斯套娃信封问题

问题抽象： 给定一个二维整数数组 envelopes（envelopes[i] = [wi, hi] 表示第 i 个信封的宽度和高度），需找到最大数量的信封序列使其满足 俄罗斯套娃嵌套规则（前一个信封可完全装入后一个信封），满足以下核心需求：

1. 嵌套规则：

   • 信封 A 可装入信封 B 当且仅当 A.width < B.width 且 A.height < B.height（严格小于）；
   • 序列中相邻信封必须满足嵌套关系（如 [2,3] → [5,6] → [7,8]）。

2. 优化目标：

   • 求 最长嵌套信封序列的长度（非连续子数组）；
   • 序列中信封需按嵌套关系严格递增排序（宽度和高度均递增）。

3. 关键转换：

   • 问题等价于 二维最长递增子序列（LIS）：
     • 先按宽度 升序排序；
     • 宽度相同时，按高度 降序排序（避免同宽度信封被错误嵌套）；
     • 在高度序列中求 严格递增子序列（LIS）。

4. 边界处理：

   • 空输入：返回 0；
   • 单信封：返回 1；
   • 同尺寸信封：[[1,1],[1,1]] 返回 1（无法嵌套）；
   • 交叉尺寸：
     • [[5,4],[6,4],[6,7],[2,3]] → 最长序列 [[2,3]→[5,4]→[6,7]]（长度 3）；
     • [[1,3],[3,5],[6,7],[6,8],[8,4],[9,5]] → 最长序列 [[1,3]→[3,5]→[6,7]→[9,5]]（长度 4）。

5. 计算约束：

   • 时间复杂度 O(n log n)（避免暴力 O(n²)，需用贪心+二分优化 LIS）；
   • 空间复杂度 O(n)（存储排序后序列及 LIS 辅助数组）；
   • 处理大规模数据：信封数量 n ≤ 10^5。

输入：二维整数数组 envelopes（1 ≤ envelopes.length ≤ 10^5，1 ≤ wi, hi ≤ 10^5）
输出：最大嵌套信封序列长度（整数）。

解题思路

问题本质：将二维嵌套问题转化为一维最长递增子序列（LIS）问题
关键步骤：

1. 特殊排序：
   • 按宽度 升序排序
   • 宽度相同时，按高度 降序排序（避免相同宽度的信封被错误嵌套）
2. 问题转化：
   • 排序后提取所有高度值形成新数组
   • 问题转化为求该高度数组的 最长严格递增子序列（LIS）
3. LIS优化：
   • 使用 贪心 + 二分查找 算法（时间复杂度 O(n log n)）
   • 维护 tail 数组：tail[i] 表示长度为 i+1 的递增子序列的最小末尾值
   • 遍历高度值，通过二分查找确定每个值在 tail 中的位置

代码实现（Java版）🔥点击下载源码

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // 边界检查
        if (envelopes == null || envelopes.length == 0) return 0;
        
        // 1. 特殊排序：宽度升序，相同宽度时高度降序
        Arrays.sort(envelopes, (a, b) -> 
            a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]
        );
        
        // 2. 提取高度值形成新数组
        int n = envelopes.length;
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = envelopes[i][1];
        }
        
        // 3. 使用贪心+二分查找求LIS长度
        return lengthOfLIS(heights);
    }
    
    private int lengthOfLIS(int[] nums) {
        int len = 0;  // 当前LIS长度
        int[] tail = new int[nums.length];  // 存储递增子序列的最小末尾值
        
        for (int num : nums) {
            // 二分查找：找到第一个 >= num 的位置
            int left = 0, right = len;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tail[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 更新tail数组
            tail[left] = num;
            // 如果扩展了序列长度
            if (left == len) len++;
        }
        return len;
    }
}

代码说明

1. 排序处理：

   • Arrays.sort(envelopes, (a, b) -> ...) 实现核心排序逻辑
   • 宽度不同时升序：a[0] - b[0]
   • 宽度相同时降序：b[1] - a[1]（关键避免同宽度嵌套）

2. 高度提取：

   • 遍历排序后的信封数组，提取所有高度值存入 heights 数组
   • 此时问题已转化为标准的LIS问题

3. LIS优化算法：

   • tail 数组：tail[i] 存储长度为 i+1 的递增子序列的最小末尾值
   • 二分查找：
     • 若当前值 num 大于 tail 末尾值 → 直接追加到末尾（len++）
     • 否则在 tail[0..len-1] 中找到第一个 >=num 的位置并替换
   • 时间复杂度：O(n log n)，满足性能要求

提交详情（执行用时、内存消耗）