20210304 354. 俄罗斯套娃信封问题

题目

https://leetcode-cn.com/problems/russian-doll-envelopes/

题解

这个题可以看成是求最长递增子序列的变题,一旦把(x,y)的x先做排序之后,剩下的问题就是如何求y的最大递增子序列,并且递增子序列中x不可以相等

如何求一个一维数组的递增子序列

d[i]表示以i结尾的最长子序列,所以只要能找到d[0~i-1]之间的k,d[k]<d[i]并且d[k]是max(d[0~i-1]),那么d[i] = d[k]+1

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }
    });
    int max = 0;
    int dp[] = new int[envelopes.length];
    dp[0] = 1;
    for (int i = 1; i < envelopes.length; i++) {
        int tmpMax = 1;
        for (int j = i - 1; j >= 0; j--) {
            if (envelopes[i][1] > envelopes[j][1] && envelopes[i][0] > envelopes[j][0]) {
                tmpMax = Math.max(tmpMax, dp[j] + 1);
            }
        }
        dp[i] = tmpMax;
        max = Math.max(tmpMax, max);
    }
    return max;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注