动态规划困难1 种解法

#354俄罗斯套娃信封问题

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

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

解题主线

先按宽升序排序，把二维偏序降为高度上的最长严格递增子序列。

宽相同时必须按高降序排列，使同宽信封的高度不可能在严格递增子序列中被连续选中。

排序后应用第 300 题的 LIS 动态规划即可得到嵌套数量。

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

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

时间复杂度

O(n²)，排序 O(n log n) 被 LIS 主导

空间复杂度

O(n)

354. 俄罗斯套娃信封问题 · 宽升高降排序加 LIS

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++) {
            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;
    }
}

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

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

边界与易错点

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

整理来源

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

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