LeetCode 354:俄罗斯信封套娃问题

题目

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

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

说明: 不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

思路

来源:labuladong

这道题目其实是最长递增子序列 (Longes Increasing Subsequence, 简写为 LIS) 的一个变种,因为很显然,每次合法的嵌套都是大的套小的,相当于找一个最长递增的子序列,其长度就是最多能嵌套的信封个数。

但是难点在于,标准的LIS算法只能在数组中寻找最长子序列,而我们的信封是由[w, h]这样的二维数对形式表示的,如何把LIS算法运用过来呢?

w * h计算面积的形式是行不通的,1 * 10 大于 3 * 3,但是明显这样的两个信封是无法相互嵌套的。

解法

这道题的解法是比较巧妙的:

先对宽度 w 进行升序排列,如果遇到 w 相同的情况,则按照高度 h 降序排列。之后把所有的 h 取出,填入一个数组,在这个数组上计算 LIS 的长度就是我们的答案。

示例:

1
2
3
4
5
6
7
8
9
|  宽度w   高度h
|  [ 1  ,  8 ] 
|  [ 2  ,  3 ]
|  [ 5  ,  4 ]|降
|  [ 5  ,  2 ]|序
|  [ 6  ,  7 ]|降
|  [ 6  ,  4 ]|序

很明显,高度 h 组成的数组中 3 -> 4 -> 7 ,就是我们要找的LIS,其最大长度为3

这个解法的关键在于,对于宽度 w 相同的数对,要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的,逆序排序保证 w 相同的数对中最多只选取一个。

代码

 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

func maxEnvelopes(envelopes [][]int) int {
	count := len(envelopes)

	// 快速排序
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] > envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})

	// 取出h
	height := make([]int, count)
	for i := 0; i < count; i++ {
		height[i] = envelopes[i][1]
	}

	// 计算LIS
	return lengthOfLIS(height)
}

// LIS 计算
func lengthOfLIS(nums []int) int {
	piles, count := 0, len(nums)
	top := make([]int, count)

	for i := 0; i < count; i++ {
		num := nums[i]
		left, right := 0, piles

		for left < right {
			mid := (left + right) / 2
			if top[mid] >= num {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left == piles {
			piles++
		}
		top[left] = num
	}
	return piles
}

wiki

最长递增子序列扩展到二维而已

动态规划设计方法&&纸牌游戏讲解二分解法