354. Russian Doll Envelopes

DP(TLE)

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
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (o1, o2) -> {
            int diff = o1[0] - o2[0];
            if (diff == 0) {
                return o2[1] - o1[1]; // 宽度相同时高度降序可以在计算时避免比较宽度，只需比较高度即可
            } else {
                return diff;
            }
        });

        int n = envelopes.length;
        int res = 0;
        // 定义 dp[i] 为 envelopes[i] 能容纳下多少个信封
        int[] dp = new int[n];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }

        return res + 1;
    }
}

DP

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
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (o1, o2) -> {
            int diff = o1[0] - o2[0];
            if (diff == 0) {
                return o2[1] - o1[1]; // 注意宽度相同时根据高度降序以避免将宽度相同的信封装入
            } else {
                return diff;
            }
        });

        int n = envelopes.length;
        int[] tails = new int[n];
        int nextIndex = 0;
        for (int[] envelope : envelopes) {
            int height = envelope[1];
            int insertIndex = findInsertIndex(tails, 0, nextIndex - 1, height);
            tails[insertIndex] = height;
            if (insertIndex == nextIndex) {
                nextIndex++;
            }
        }

        return nextIndex;
    }

    private int findInsertIndex(int[] tails, int left, int right, int target) {
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (tails[mid] < target) {
                left = mid + 1;
            } else if (tails[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        // now: [right, left]
        return left;
    }
}

难点在于对高度进行逆序排序并转换为 LIS 问题。

References

354. Russian Doll Envelopes