leetcode-354 - 动态规划 - leetcode

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 <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

# 解题思路 🤔

这道题是俄罗斯套娃信封问题，主要思路如下：

首先对信封按照宽度进行排序，如果宽度相同，则按照高度降序排序
将问题转化为在高度数组中寻找最长递增子序列 (LIS) 的问题
使用二分查找优化 LIS 的求解过程，时间复杂度从 O (n²) 优化到 O (nlogn)

# 代码实现 💻

	// 主函数：计算最多能嵌套的信封数量
	func maxEnvelopes(envelopes [][]int) int {
	n := 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]
	})

	// 提取所有信封的高度，形成新的数组
	height := make([]int, n)
	for i := 0; i < n; i++ {
	height[i] = envelopes[i][1]
	}

	// 求解最长递增子序列
	return lengthOfLIS(height)
	}

	// 使用二分查找优化求解最长递增子序列
	func lengthOfLIS(nums []int) int {
	// 存储每个牌堆顶部的牌
	top := make([]int,len(nums))
	// 牌堆数初始化为 0
	piles := 0

	for i:=0; i<len(nums);i++{
	// 要处理的扑克牌
	poker := nums[i]
	// 搜索左侧边界的二分查找
	var left, right = 0,piles
	for left < right{
	mid := (left+right)/2
	if top[mid] > poker {
	right = mid
	}else if top[mid]< poker{
	left = mid + 1
	}else{
	right = mid
	}
	}
	// 没有找到合适的牌堆，新建一堆
	if left == piles{
	piles++
	}
	// 把这张牌放到牌堆顶
	top[left] = poker
	}
	// 牌堆数就是 LTS 长度
	return piles
	}

# 复杂度分析 📊

时间复杂度：O (nlogn)，其中 n 是信封的数量
空间复杂度：O (n)，需要存储排序后的高度数组和牌堆数组

# 总结 💡

这道题的关键在于：

将二维问题转化为一维问题
使用排序和二分查找优化求解过程
理解 LIS 的二分查找解法

# 解题思路 🤔

# 代码实现 💻

# 复杂度分析 📊

# 总结 💡

leetcode-300