【3.4】LeetCode每日一题· 俄罗斯套娃信封问题

2021年03月04日 10时46分

标签： LeetCode 动态规划最长上升子序列二分

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

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

####说明
不允许旋转信封。

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

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/russian-doll-envelopes "题目链接")

## 解题思路和代码
不妨首先将所有信封的宽度排序，这样只需要考虑所有“套娃”的信封长度从小到大排序得到的序列最长即可，也就是最长上升子序列。
但是由于题目的“套娃”严格要求前一个信封的宽度小于后一个信封的宽度，对宽度排序时，对宽度相同的信封可能会出现问题。例如只对宽度排序，可能得到
	
	[[1, 1], [1, 2], [1, 3]]
再考虑长度的最长上升子序列，会得到答案为3，但实际上答案为1，因为宽度相同的信封不能进行“套娃”。
考虑到这一点，我们可以在对宽度排序时，如果两个信封宽度相同，那么就按照长度**从大到小**排序，例如原来的排序就变成了

[[1, 3], [1, 2], [1, 1]]
这样相同宽度的信封的最长上升子序列的长度只能是**1**，巧妙的解决了这一问题。
那么问题就变成了如何求解最长公共子序列，可以使用DP（时间复杂度$$O(N^2)$$）或贪心+二分（时间复杂度$$O(N\log N)$$）两种方式。

### 动态规划
设`dp[i]`表示`考虑第0~i个信封，且取第i个信封的最长上升子序列长度`，可以得到递推公式

```math
\displaystyle
dp[i] = \max\{ dp[k] | k < i  \wedge envelope[k][1] < envelope[i][1] \} + 1
```

即，当我们**必须要**选择第`i`个信封作为子序列的最后一个元素时，需要考虑其之前的所有第`k, 0 <= k < i`个信封为子序列的最后一个元素，如果`k`的长度（`envelope[k][1]`）小于`i`的长度（`envelope[i][1]`），那么可以把`i`放在`k`的后面，形成长度+1的新的最长子序列。
最后考察以每个信封作为子序列的最后一个元素时序列的长度，其最大值即为最长公共子序列的长度。
因此可以得到代码：

class Solution {
	public:
		static bool cmp(vector<int> v1, vector<int> v2){
			if(v1[0] != v2[0]){
				return v1[0] < v2[0];
			}
			else{
				return v1[1] > v2[1];
			}
		}
		int maxEnvelopes(vector<vector<int>>& envelopes) {
			sort(envelopes.begin(), envelopes.end(), cmp);
			vector<int> dp(envelopes.size());
			// dp[i] := 以envelops[i][1] 为结尾的最长子序列长度
			// dp[i] = max{dp[k]|envelops[k][1] < envelops[i][1], k < i} + 1,
			for(int i = 0; i < envelopes.size(); i++){
				dp[i] = 1;
				for(int k = 0; k < i; k++){
					if(envelopes[k][1] < envelopes[i][1]) dp[i] = max(dp[i], dp[k]+1);
				}
			}
			int res = 0;
			for(int i = 0; i < envelopes.size(); i++){
				res = max(res, dp[i]);
			}
			return res;
		}
	};

#### 用时和内存
> 执行用时：1212 ms，在所有 C\++提交中击败了35.73%的用户
> 内存消耗：46.6 MB，在所有 C\++提交中击败了15.98%的用户

### 贪心+二分
考虑一个简单的贪心：对于长度越长的上升子序列，其最后一个元素的大小应该越小。记`f[j]`为上升子序列长度为`j`时子序列的最后一个元素。可以证明，`f[]`是单调递增的（长度越长的上升子序列，其最后一个元素一定越大）。我们对所有的信封进行遍历，迭代地构造出`f[]`数组。
* 如果当前遍历到的信封长度`h`大于当前`f[]`数组的最后一个元素（也就是最长子序列的最后一个信封的长度），显然可以将`h`放在`f[]`的最后，构造出一个长度+1的更长的上升子序列。
* 否则，考虑到贪心，我们找到`f[]`中第一个不小于`h`的位置`i`，此时`h`和`i`满足

$$f[i-1] < h \leq f[i]$$

因此我们可以缩小`f[i]`为`h`从而实现贪心。考虑到`f[]`的单调性，可以使用二分搜索来找到`i`的位置。最长公共子序列的个数，也就是`f[]`下标`j`的最大值，亦即`f[]`的长度。因此可以得到如下代码
		
	class Solution {
	public:
		static bool cmp(vector<int>& v1, vector<int>& v2){
			if(v1[0] != v2[0]){
				return v1[0] < v2[0];
			}
			else{
				return v1[1] > v2[1];
			}
		}
	
		// 找到不大于h的第一个下标
		int binaryFind(vector<int>& f, int h){
			int l = 0, r = f.size()-1;
			while(l <= r){
				int mid = ((r-l)>>1) + l;
				if(f[mid] < h){
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}
			return l;
		}
	  
		int maxEnvelopes(vector<vector<int>>& envelopes) {
			if(envelopes.size() == 0) return 0;
			sort(envelopes.begin(), envelopes.end(), cmp);
			vector<int> f;
			f.push_back(envelopes[0][1]);
			for(int i = 1; i < envelopes.size(); i++){
				int& h = envelopes[i][1];
				if(h > f.back()){
					f.push_back(h);
				}else{
					int index = binaryFind(f, h);
					f[index] = h;
				}
			}
			return f.size();
		}
	};

#### 用时和内存
> 执行用时：36 ms，在所有 C\++提交中击败了97.75%的用户
> 内存消耗：13.3 MB，在所有 C\++提交中击败了96.94%的用户

### lower\_bound内置函数
实际上，C\++的STL库提供了找到某一序列中第一个不小于`h`的位置（迭代器）的函数`lower_bound`，这样就可以避免手写二分带来错误的可能。
注意`lower_bound`返回的是一个迭代器（指针），因此修改其地址上存储的值需要使用取值运算符`*`。
	
	class Solution {
	public:
		static bool cmp(vector<int>& v1, vector<int>& v2){
			if(v1[0] != v2[0]){
				return v1[0] < v2[0];
			}
			else{
				return v1[1] > v2[1];
			}
		}
		int maxEnvelopes(vector<vector<int>>& envelopes) {
			if(envelopes.size() == 0) return 0;
			sort(envelopes.begin(), envelopes.end(), cmp);
			vector<int> f;
			f.push_back(envelopes[0][1]);
			for(int i = 1; i < envelopes.size(); i++){
				int& h = envelopes[i][1];
				if(h > f.back()){
					f.push_back(h);
				}else{
					vector<int>::iterator pos = lower_bound(f.begin(), f.end(), h);
					*pos = h;
				}
			}
			return f.size();
		}
	};

#### 用时和内存
> 执行用时：36 ms，在所有 C\++提交中击败了97.75%的用户
> 内存消耗：13.3 MB，在所有 C\++提交中击败了90.01%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.4】LeetCode每日一题· 俄罗斯套娃信封问题

所有评论

暂无评论

新增评论