数据结构学习 Leetcode356 俄罗斯套信封

发布时间:2023年12月26日

关键词:动态规划 最长递增子序列 贪心 二分查找

其实就是最长递增子序列。比较难的是需要理解题目用并想起来用这个方法。

可以看看这位大神写的方法,循序渐进,我觉得很好。

里面提到的四种方法的总结就是:

  • 第一种方法就是降维(控制第一维)+最长上升子序列。
  • 第二种方法就是降维(控制第一维)+最长上升子序列+控制第二维
  • 第三种方法就是降维(控制第一维)+贪心。
  • 第四种方法就是降维(控制第一维)+贪心+二分查找。

我在下面写的解法一 对应 第一种方法。

?我在下面写的解法二 对应 第四种方法。

题目:

解法一:暴力的最长递增子序列

这个方法,我做到某个用例的时候超时了。

思路:

降维:一般的最长递增子序列只能用于一维,然而这个是二维的,所以我们可以控制第一维(给第一维排序),然后对第二位进行最长递增子序列的计算。

控制第一维的理由:

状态和转移方程:

复杂度计算:

时间复杂度O(n^2) 排序nlogn 遍历并求最大值n^2

空间复杂度O(n) dp列表

代码:

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        std::sort(envelopes.begin(),envelopes.end());
        vector<int> dp(envelopes.size());
        int result=0;
        for(int i=0;i<envelopes.size();++i)
        {
            int max=0;
            for(int j=0;j<i;++j)
            {
                if(envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1])
                {
                    max=std::max(max,dp[j]+1);
                }
            }
            dp[i]=max;
            result=std::max(max,result);
        }
        return result+1;
    }
};

解法二:贪心 二分查找

这个方法基本和我之前学的最长上升子序列的题目一样,我有写笔记,这个对应笔记的方法二。

这个方法其实就是我最上面给到的链接的第四种方法。第四种方法其实是第2 3种方法的优化版本。

思路:

具体思路看我提供的链接吧。

关键就是开一个序列存最小的状态。然后二分。

复杂度计算:

时间复杂度O(nlogn) 排序nlogn,遍历信封列表需要 O(N),计算每一个信封插入位置需要?O(logN)

空间复杂度O(n) dp列表

代码:

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        std::sort(envelopes.begin(),envelopes.end(),[](vector<int>&a,vector<int>&b)
        {
            if(a[0]==b[0]) return a[1]>b[1];
            return a[0]<b[0];
        });
        vector<int> dp(envelopes.size());
        int len=0;
        dp[0]=envelopes[0][1];
        for(int i=1;i<envelopes.size();++i)
        {
            if(dp[len]<envelopes[i][1])
            {
                len++;
                dp[len]=envelopes[i][1];
            }
            else if(dp[len]>envelopes[i][1])
            {
                int l=0;
                int r=len;
                while(l<r)
                {
                    int mid=(r+l)/2;
                    if(envelopes[i][1]>dp[mid])
                    {
                        l=mid+1;
                    }
                    else
                    {
                        r=mid;
                    }
                }
                dp[r]=envelopes[i][1];
            }
        }
        return len+1;
    }
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135216851
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。