0%

信封嵌套问题

发表于 分类于
本文字数： 阅读时长 ≈

给定一个N行2列的二维数组arr，每一个小数组的两个值分别代表一个信封的长和宽，如果信封A的长和宽小于信封B，那么信封A可以放在信封B里，返回信封最多可以嵌套多少层。

例：arr = {
{3,4}
{2,3}
{4,5}
{1,3}
{2,3}
{3,6}
{1,2}
{3,2}
{2,4}
}
信封最多可以嵌套4层，从里到外分别是{1,2} {2,3} {3,4} {4,5}，所以返回4。
此问题与最长增长子序列问题思想类似。

把N个长度为2的小数组变成信封数组。然后对信封数组排序，排序的策略为：按照长度从小到大排序，长度相等的信封之间按照宽度从大到小排序，代码如下：
//定义信封类以及信封的长和宽信息

1
2
3
4
5
6
7
8
9
class Envelope {
	public int len;
	public int wid;
	
	public Envelope (int len,int wid) {
		this.len = len;
		this.wid = wid;
	}
}

//定义类进行信封的比较

1
2
3
4
5
6
7
8
class EnvelopeComparator implements Comparator<Envelope> {

	@Override
	public int compare(Envelope o1, Envelope o2) {
		// TODO Auto-generated method stub
		return o1.len != o2.len ? o1.len - o2.len : o2.wid - o1.wid;
	}	
}
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
43
44
45
46
class MostEnvelope {
	
	public static Envelope[] getSortedEnvelopes (int[][] matrix) {
		Envelope[] res = new Envelope[matrix.length];
		for (int i = 0; i < matrix.length; i++) {
			res[i] = new Envelope(matrix[i][0], matrix[i][1]);
		}
		Arrays.parallelSort(res,new EnvelopeComparator());
		return res;
	}
	//这是主方法
	public static int maxEnvelopes(int[][] matrix) {
		Envelope[] envelopes = getSortedEnvelopes(matrix);
		int[] ends = new int[matrix.length];
		ends[0] = envelopes[0].wid;
		
		int right = 0;
		int l = 0;
		int r = 0;
		int m = 0;
		for (int i = 1;i < envelopes.length;i++) {
			l = 0;
			r = right;
			while (l <= r) {
				m = (l + r) / 2;
				if (envelopes[i].wid >ends[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			right = Math.max(right, l);
			ends[l] = envelopes[i].wid;
		}
		return right + 1;
	}
    //测试代码
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        //定义数组
		int[][] matrix = { {2,3},{4,5},{3,4},{2,2},{2,4},{3,6}};
		System.out.println(maxEnvelopes(matrix));
		
	}

}