• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

套娃信封问题

开发技术 开发技术 3小时前 2次浏览

链接

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

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

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

注意:不允许旋转信封。

import java.util.Arrays;
import java.util.Comparator;

class Solution {

    private int search(int[] dp, int length, int key) {
        int l = 0, r = length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (dp[mid] < key) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) {
            return 0;
        }

        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? Integer.compare(o2[1], o1[1]) : Integer.compare(o1[0], o2[0]);
            }
        });

        int[] dp = new int[envelopes.length];
        int length = 1;
        dp[0] = envelopes[0][1];

        for (int i = 1; i < envelopes.length; ++i) {
            int index = search(dp, length, envelopes[i][1]);
            dp[index] = envelopes[i][1];
            if (index == length) {
                length++;
            }
        }

        return length;
    }
}

程序员灯塔
转载请注明原文链接:套娃信封问题
喜欢 (0)