做袜子娃娃的网站,wordpress 文章卡片,wordpress按钮下拉,做一个搜索引擎网站要多少钱354. 俄罗斯套娃信封问题 - 力扣#xff08;LeetCode#xff09;
给你一个二维整数数组 envelopes #xff0c;其中 envelopes[i] [wi, hi] #xff0c;表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候#xff0c;这个信封就可以放进另一…354. 俄罗斯套娃信封问题 - 力扣LeetCode
给你一个二维整数数组 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 105envelopes[i].length 21 wi, hi 105
首先按照朴素的dp思想
先定义每一个信封的状态,无非是选择或者不选择。
int dp[n]; 选择第i个信封最多可以嵌套的数量.
在按照 sort(envelopes.begin(),envelopes.end(),[](auto x, auto y){return x[0] y[0] ? x[1] y[1] : x[0] y[0];});
规则的排序下,可知道
若 第i个信封可以完全包裹上一个信封则进行 if(envelopes[i][1] envelopes[j][1] envelopes[i][0] envelopes[j][0]){dp[i] max(dp[i], dp[j] 1);}
否则将 dp[i]置为1
为什么置为1 ?
因为不存在当第i个信封能完全包裹一个信封的情况下会有不选择该信封的ans 选择该信封的ans
那么可以认为,要么第i个信封能包裹信封,要么将第i个信封作为一个新的开头 可得最初版的线型dp解
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(),envelopes.end(),[](auto x, auto y){return x[0] y[0] ? x[1] y[1] : x[0] y[0];});int n envelopes.size();int dp[n];memset(dp, 0, sizeof dp);dp[0] 1;for(int i 1; i n; i){for(int j i - 1; j 0; j--){if(envelopes[i][1] envelopes[j][1] envelopes[i][0] envelopes[j][0]){dp[i] max(dp[i], dp[j] 1);}}if(0 dp[i])dp[i] 1;}int ans 0;for(int i 0; i n;i)ans max(ans, dp[i]);return ans;}
}; 以上代码的时间复杂度为排序O(nlogn) O(n ^ 2)
显然对于 1 envelopes.length 105 是远远不够的
现在看看核心代码 for(int i 1; i n; i){for(int j i - 1; j 0; j--){if(envelopes[i][1] envelopes[j][1] envelopes[i][0] envelopes[j][0]){dp[i] max(dp[i], dp[j] 1);}}if(0 dp[i])dp[i] 1;}
是不是很像求最长递减子序列?
只不过是先对长or宽排序之后对宽or长序列求最长子序列即可
那我们直接用二分优化求最长子序列的方法做即可
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(),envelopes.end(),[](auto x, auto y){return x[0] y[0] ? x[1] y[1] : x[0] y[0];});int n envelopes.size();vector v {0};for(int i 0; i n; i){int k envelopes[i][1];if(k v.back()){v.emplace_back(k);}else{auto it lower_bound(v.begin(),v.end(),k);*it k;}}return v.size() - 1;}
};
