Russian Doll Envelopes

2025-05-02

leetcode, russian-doll-envelopes

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russin doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

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

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

Example 1:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

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
import java.util.*;

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // 1. 按照宽度升序，宽度相同时按高度降序排序
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] = a[1]; // 宽度相同，高度降序
            }
            return a[0] - b[0]; // 否则宽度升序
        });        
        // 2. 对高度数组求最长递增子序列(LTS)
        ArrayList<Integer> dp = new ArrayList<>();
        for (int[] envelope : envelopes) {
            int height = envelope[1];
            int idx = Collections.binarySearch(dp, height);
            if (idx < 0) {
                idx = -idx - 1;
            }
            if (idx == dp.size()) {
                dp.add(height);
            } else {
                dp.set(idx, height);
            }
        }
        return dp.size();
    }
}

信封最终被套上，里面一定是排序好的。

  • 先按宽度升序排序。
  • 宽度相同，按照高度降序排序(防止宽度相同的信封被错误嵌套)。
  • 排序后，只需在高度数组上找最长递增子序列即可。

示例1排序后的结果为 [[2, 3], [5, 4], [6, 7], [6, 4]]