LeetCode354-俄罗斯套娃信封问题

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/russian-doll-envelopes/

中文链接：https://leetcode-cn.com/problems/russian-doll-envelopes/

题目详述

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

示例:

1
2
3
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

题目详解

动态规划。问题可以转化为一个 最长上升子序列 问题。

  • 对数组进行排序，按 w 升序，w 相等时按 h 降序排序。
  • 接下来求 h 的 LIS 即可。
  • 排序规则说明：必须是信封宽度和高度都大于另一个信封时才能装下（[3, 3] 不能放进 [3, 4] 里面），所以在排序时 [3, 4] 要放在 [3, 3] 前面。

LIS 的时间复杂度为 O(n^2) 的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LeetCode_00354 {

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return Integer.compare(o1[0], o2[0]);
                }
                return Integer.compare(o2[1], o1[1]);
            }
        });
        int n = envelopes.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = dp[0];
        for (int d : dp) {
            res = Math.max(res, d);
        }
        return res;
    }
}

LIS 的时间复杂度为 O(nlogn) 的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class LeetCode_00354 {

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return Integer.compare(o1[0], o2[0]);
                }
                return Integer.compare(o2[1], o1[1]);
            }
        });
        int[] dp = new int[envelopes.length];
        int len = 0;
        for (int[] envelope: envelopes) {
            int i = Arrays.binarySearch(dp, 0, len, envelope[1]);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = envelope[1];
            if (i == len) {
                ++len;
            }
        }
        return len;
    }
}