俄罗斯套娃信封问题

发表于 | 更新于 | 分类于 |
本文字数： 5.7k | 阅读时长 ≈ 5 分钟

写在前面

本篇文章源于牛客网在9月13号晚上左神（左程云）的直播内容，在这对里面的俄罗斯套娃信封问题做一个课后总结，也对这个思路及代码做一个梳理。

题目

题目在leetcode354上也有描述，也是Google面试题。下面我进行中文的描述：

见过俄罗斯套娃吗？如图所示，大的娃娃可以套在小的外面，这样就可以把多个娃娃套在一起。

俄罗斯套娃

现在有很多信封，每个信封有宽度和高度[w,h]，只有宽度和高度都比其他信封大的时候才能够套在别的信封的外面。那么最多多少个信封可以像俄罗斯套娃那样套在一起？

例子

给你信封
envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]],
则最多可以向俄罗斯套娃那样套在一起的信封数为3。([2, 3] => [5, 4] => [6, 7]).

算法分析

首先我们从两种情况来讨论这个问题:

  • w无重复值（即信封的宽度每个信封都不一样）
  • w可以重复（即信封的宽度存在一样的，题目就是这种情况）

针对情况I

当每个信封的宽度和高度不一样时，我们可以对信封按照宽度从小到大进行排序，比如针对信封[[3,2],[2, 4],[4,3],[5, 6],[6,5]排序后变为
w: 2 -> 3 -> 4 -> 5 -> 6
h: 4 -> 2 -> 3 -> 6 -> 5

此时，因为信封的宽度w已经是从小到大排列了，要想信封可以套，这要求关于信封高度h的数组[4, 2, 3, 6, 5]是的子序列是递增的，且要求是最长的（题目要求的是最多的信封），所以可以转化为另一个问题：给定数组，求它的最长递增子序列（也称最长上升子序列）。关于这个问题在leetcode300有具体描述。

最长递增子序列

比如给的数组arr = [3, 1, 2, 5, 4, 6]。
得到的最长递增子序列长度为4，即[1, 2, 5, 6]或[1, 2, 4, 6]。
这个问题的解法是动态规划，给一个相同长度的数组dp，dp[i]表示以arr[i]结尾的最长递增子序列，初始化都为1(本身构成最长递增子序列)，即dp[i] = 1, 这个的动态转移方程（递推式）为，j从0到i - 1，如果arr[i] > arr[j], 这dp[i] = max(dp[i], dp[j] + 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 求最长递增子序列方法
public static int[] lis1(int[] arr) {
	if (arr == null || arr.length == 0) {
		return null;
	}
	int[] dp = getdp1(arr);
	return generateLIS(arr, dp);
}

// 动态规划
public static int[] getdp1(int[] arr) {
	int[] dp = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = Math.max(dp[i], dp[j] + 1);
			}
		}
	}
	return dp;
}

// 返回一个最长递增子序列（由动态规划产生的dp数组）
public static int[] generateLIS(int[] arr, int[] dp) {
	int len = 0;
	int index = 0;
	for (int i = 0; i < dp.length; i++) {
		if (dp[i] > len) {
			len = dp[i];
			index = i;
		}
	}
	int[] lis = new int[len];
	lis[--len] = arr[index];
	for (int i = index; i >= 0; i--) {
		if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
			lis[--len] = arr[i];
			index = i;
		}
	}
	return lis;
}

上面这种算法的最差情况下的算法复杂度是O($n^2$)。下面介绍一种优化的方式。

除了数组dp，即dp[i]表示以arr[i]结尾的最长递增子序列长度。再引入一个数组ends，初始长度和arr相等。ends[i]表示长度为i + 1的所有递增子序列的最小结尾。
举个栗子：
arr: [3, 1, 2, 4, 3]

  1. 当i = 0时， 显然dp[0] = 1，此时长度为1的最长递增子序列的最小结尾为3，因为后面还没有遍历到。即ends[i] = 3；
  2. 当i = 1时，显然dp[1] = 1，以1结尾的最长递增子序列为1，此时没有长度为2的最长递增子序列，只有长度为1的最长递增子序列，然后最小结尾已经改变，1此时是最长递增子序列长度为1的最小结尾。即此时end[0] = 1
  3. 当i = 2时，显然dp[2] = 2， 此时有长度为2的最长递增子序列，且最小结尾为2，长度为1的最小结尾为1。
    …
    …

依次类推
最后结果:
ends: [1, 2, 3]
dp: [1, 1, 2, 3, 3]

总结下数组ends和dp的更新策略，当遍历到arr[i]时，用arr[i]去ends前面有查找ends[j]刚好大于或等于arr[i]的那个值并替换，如果没有，则在ends后面添加arr[i]。这个查找可以使用二分查找提高效率。而对于dp[i]的更新，只需查看数组ends数组里面arr[i]及其左边的长度，dp[i]就等于ends里面arr[i]的下标+1。

数组更新完成后，后面的算法都是一样的，dp[i]里面的最大值即为最长递增子序列。

具体代码如下：

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
public static int[] lis2(int[] arr) {
	if (arr == null || arr.length == 0) {
		return null;
	}
	int[] dp = getdp2(arr);
	return generateLIS(arr, dp);
}

public static int[] getdp2(int[] arr) {
	int[] dp = new int[arr.length];
	int[] ends = new int[arr.length];
	ends[0] = arr[0];
	dp[0] = 1;
	int right = 0;
	int l = 0;
	int r = 0;
	int m = 0;
	for (int i = 1; i < arr.length; i++) {
		l = 0;
		r = right;
		while (l <= r) {
			m = (l + r) / 2;
			if (arr[i] > ends[m]) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		right = Math.max(right, l);
		ends[l] = arr[i];
		dp[i] = l + 1;
	}
	return dp;
}

这种方式的最坏情况的时间复杂度为$O(n\log n)$。

解决了最长递增子序列的问题，那么这种情况基本就解决了，具体代码就不贴出来了。

针对情况Ⅱ

对于情况Ⅱ，我们首先像情况I一样考虑，对信封的宽度w按从小到大排序，那么此时面临一个问题，对于相同宽度的信封的高h怎么进行排序，如果我们也按照从小到大排序，那么此时按照信封高求出来的最长递增子序列有可能存在宽度w相同的情况。
举个栗子：
当宽度w = 1时， 此时有3个信封，h = 2, 3, 4
当宽度w = 2时，此时有两个信封，h = 3, 6
按照上面的排序方式排序后，
w: 1 -> 1 -> 1 -> 2 -> 2
h: 2 -> 3 -> 4 -> 3 -> 6
此时数组h的最长递增子序列为[2, 3, 4, 6]显然不符合条件。所以这种排序方式是错误的。

那么正确的排序方式是什么样的呢，就是当w相同时，h逆序，从大到小排列，这样你可以想一下，针对h求出来的最长递增子序列不会存在w相等，而h递增的情况，因为w相同的时候，右边的数总是小于等于左边的数，不会出现在最长递增子序列里面。
还是上面那个栗子排序后：
w: 1 -> 1 -> 1 -> 2 -> 2
h: 4 -> 3 -> 2 -> 6 -> 3
此时数组h的最长递增子序列长度为2（[4, 6]或[3, 6]或者其他），即最多有两个信封可以套。
具体代码如下：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class RussianDollEnvelopes {

	public static class Dot {
		public int w;
		public int h;

		public Dot(int weight, int hight) {
			w = weight;
			h = hight;
		}
	}

	public static class DotComparator implements Comparator<Dot> {
		@Override
		public int compare(Dot arg0, Dot arg1) {
			if (arg0.w != arg1.w) {
				return arg0.w - arg1.w;
			} else {
				return arg1.h - arg0.h;
			}
		}
	}

	public static int maxEnvelopes(int[][] es) {
		if (es == null || es.length == 0 || es[0] == null || es[0].length != 2) {
			return 0;
		}
		Dot[] dots = new Dot[es.length];
		for (int i = 0; i < es.length; i++) {
			dots[i] = new Dot(es[i][0], es[i][1]);
		}
		Arrays.sort(dots, new DotComparator());
		int[] ends = new int[es.length];
		ends[0] = dots[0].h;
		int right = 0;
		int l = 0;
		int r = 0;
		int m = 0;
		for (int i = 1; i < dots.length; i++) {
			l = 0;
			r = right;
			while (l <= r) {
				m = (l + r) / 2;
				if (dots[i].h > ends[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			right = Math.max(right, l);
			ends[l] = dots[i].h;
		}
		return right + 1;
	}

	public static void main(String[] args) {
		int[][] test = { { 4, 3 }, { 1, 2 }, { 5, 7 }, { 5, 3 }, { 1, 1 }, { 4, 9 } };
		System.out.println(maxEnvelopes(test));
	}
}

至此，俄罗斯套娃信封问题就解决了。

总结一下

这个问题主要在两个地方，一个是最长递增子序列的优化，二是当信封宽度相同时，信封高度h逆序排列。需要好好体会学习下。

欢迎大家交流和批评指正！

您的支持将鼓励我继续创作！