动态规划困难1 种解法

#354俄罗斯套娃信封问题

每个信封必须在宽和高两个维度都严格小于外层信封，求最多可嵌套数量。

#数组#排序#动态规划#最长递增子序列

原题

给你一个二维整数数组 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⁵

查看原题

解题主线

先按宽升序排序，把二维偏序降为高度上的最长严格递增子序列。
宽相同时必须按高降序排列，使同宽信封的高度不可能在严格递增子序列中被连续选中。
排序后应用第 300 题的 LIS 动态规划即可得到嵌套数量。

解法 1：宽升高降排序加 LIS

按宽升序、同宽按高降序排序，再用 O(n²) 动态规划求高度数组的最长严格递增子序列。

时间复杂度： O(n²)，排序 O(n log n) 被 LIS 主导
空间复杂度： O(n)

JAVA

import java.util.Arrays;

final class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) return 0;

        // 同宽时按高度降序，阻止同宽信封进入高度严格递增子序列。
        Arrays.sort(envelopes, (first, second) -> {
            int byWidth = Integer.compare(first[0], second[0]);
            return byWidth != 0
                ? byWidth
                : Integer.compare(second[1], first[1]);
        });

        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        int maximum = 1;
        for (int i = 0; i < envelopes.length; i++) {
            // dp[i] 表示以第 i 个信封结尾的最长嵌套链长度。
            for (int j = 0; j < i; j++) {
                // 宽度次序已由排序保证，这里只需检查高度严格递增。
                if (envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maximum = Math.max(maximum, dp[i]);
        }
        return maximum;
    }
}

实现提示

Arrays.sort 会原地重排 envelopes；如需保留输入顺序，应先深复制二维数组。

边界与易错点

本题真实难度是困难。
旧排序比较器使用 a[0] - b[0] 与 b[1] - a[1]，可能发生整数溢出；整理后使用 Integer.compare。
宽或高相等都不能嵌套，高度 LIS 必须使用严格小于。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q354_maxEnvelopes.java