LeetCode 354 Russian Doll Envelopes

LeetCode

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

1 <= envelopes.length <= 5000 envelopes[i].length == 2
* 1 <= w<sub>i</sub>, h<sub>i</sub> <= 10<sup>4</sup>

题目大意：

信封套信封，能套上的条件是内信封的宽度和高度均小于外信封。求最多有多少个信封能套在一次

算法思路：

类似于LIS，先排序宽度，高度就变成LIS问题。

注意事项：

1. 宽度和高度都是严格递增，所以排序envelopes的时候，先顺序排序宽度，再逆序排高度，逆序是防止同一宽度但高度不同的信封成为合法结果，如[3, 4], [3, 5], 高度LIS变成[4, 5]但不合法。还要注意Python语法：envelopes.sort(key=lambda x: (x[0], -x[1]))
2. 用bisect_left因为，若高度相等，原地替换并不往后加。

Python代码：

def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
	envelopes.sort(key=lambda x: (x[0], -x[1])) # remember format and reversed order
	sorted_height = []
	for i in range(len(envelopes)):
		index = bisect.bisect_left(sorted_height, envelopes[i][1]) # remember left
		if index < len(sorted_height):
			sorted_height[index] = envelopes[i][1]
		else:
			sorted_height.append(envelopes[i][1])
	return len(sorted_height)

Java代码：

public int maxEnvelopes(int[][] envelopes) {
	if(envelopes == null || envelopes.length == 0 || 
			envelopes[0] == null || envelopes[0].length != 2) // remember for 2d array
		return 0;
	Arrays.sort(envelopes, new Comparator<int[]>() {
		public int compare(int[] a, int[] b) {
			if(a[0] == b[0])
				return b[1] - a[1]; // remember the reverse order for [4,5], [4,6] case must strictly increasing for width and height
			else
				return a[0] - b[0];
		}
	});
	int len = 0;
	int[] lis = new int[envelopes.length];
	for(int[] e : envelopes) {
		int index = Arrays.binarySearch(lis, 0, len, e[1]);
		if(index < 0) {
			index = -index - 1;
			lis[index] = e[1];
		}
		else
			lis[index] = e[1];
		if(index == len)
			len++;
	}

	return len;
}

算法分析：

Insert时间复杂度为O(nlogn)，空间复杂度O(1)