354. 俄罗斯套娃信封问题

题目

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

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

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

注意：不允许旋转信封。

难度：🌟🌟🌟🌟🌟

示例 1：

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

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

• 1 <= envelopes.length <= 10⁵
• envelopes[i].length == 2
• 1 <= w_i, h_i <= 10⁵

题解

本题要求计算 最多能有多少信封 能组成一个“俄罗斯套娃”信封。我们的思路是：先按信封宽度 width 对这些信封进行排序，其中如果信封宽度 width 相等，则按信封高度 height 降序排序，最后求解信封高度数组的最长递增子序列长度。

举个例子🌰
假设信封为 [5,4] [6,4] [6,7] [2,3] [5,2] [1,8]，画图如下：

然后求高度 height 的最长递增子序列：

注意事项：

1. 可以通过实现 Go 语言中的 sort.Interface 接口中的 Len、Less、Swap 方法来实现自定义数组排序
2. 求解最多有多少信封套娃，本质是最长递增子序列在二维数组中的问题，通过先排序，后按高度降序排序，就将二维数组问题转化为了一维数组问题，非常精妙
3. 使用二分查找能快速检索最长递增子序列长度

代码实现

// 俄罗斯套娃信封问题
// LIS 最长递增子序列
// 假设 envelopes[i] = [wi, hi]
func maxEnvelopes(envelopes [][]int) int {
	sort.Sort(Envelop(envelopes))
	var height []int
	for _, e := range envelopes {
		height = append(height, e[1])
	}
	return getLengthOfLIS(height)
}

type Envelop [][]int

func (e Envelop) Len() int {
	return len(e)
}

// Less 实现 sort.Interface 接口的比较元素方法
func (e Envelop) Less(i, j int) bool {
	// 根据 [w, h] 中的 w 升序排序
	// 两种情况需要交换元素
	// 1. wi < wj
	// 2. wi = wj && hi > hj
	return e[i][0] < e[j][0] || (e[i][0] == e[j][0] && e[i][1] > e[j][1])
}

// Swap 实现 sort.Interface 接口的交换元素方法
func (e Envelop) Swap(i, j int) {
	e[i], e[j] = e[j], e[i]
}

// getLengthOfLIS 查找最长递增子序列长度
func getLengthOfLIS(nums []int) int {
	// 使用二分查找排序找到对应位置，思路类似整理顺子牌
	n := len(nums)
	length := 0
	top := make([]int, n)
	for i := 0; i < n; i++ {
		poker := nums[i]
		left, right := 0, length
		// 二分查找插入位置
		for left < right {
			mid := left + (right-left)/2
			if top[mid] >= poker {
				// 如果 poker 比 top 中元素小，则说明 poker 比 top[x] 更有价值，后续存在比 poker 值大的数的概率会更大
				right = mid
			} else {
				left = mid + 1
			}
		}
		// 如果查找到最右侧，则说明 top 需要扩充
		if left == length {
			length++
		}
		top[left] = poker
	}
	// 最后的 top 不一定是最长子序列，但 length 一定是最长子序列长度
	return length
}