leetcode 354. 俄罗斯套娃信封问题总结(c++实现) |
您所在的位置:网站首页 › 你知道俄罗斯套娃吗 › leetcode 354. 俄罗斯套娃信封问题总结(c++实现) |
题目描述:
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。 说明: 不允许旋转信封。 示例: 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。 解法一: 普通的dp这个解法理解起来好一些,但是效率不高. dp中的值代表以当前信封结尾的前面所有序列的最长上升子序列的长度.例如,在idx=6的位置,因为它前面的[5,400]和[5,500]的H都比[6,360]大,所以,它遍历它前面比大小的dp最大值的位置,在追加上当前值,组成当前位置的dp[6].这个过程比较耗时,因为没到一个位置,都要遍历一遍它前面的所有数. 那么,有人就想到了一个好办法,就是使用二分法找到它左边第一个比它的H大的那个数,用当前这个数替代它.例如,对于[6,360]来说,它的左边第一个比它大的数就是[5,400],则每一步都这么做的话,最终的dp长度就是所要求的结果.这就有了第二种方法.移步到->解法二. class Solution { public: int maxEnvelopes(vector& envelopes) { int n = envelopes.size(); if(n == 0) return 0; sort(envelopes.begin(), envelopes.end()); vector dp(n, 1); dp[0] = 1; int res = 1; for(int i = 1; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |