给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。-笔试面试资料

慢点卷

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]>=b[1];//宽度相等时按照高度降序排列
        else
            return a[0]<b[0];//按照宽度升序排列
    }
    int LIS(vector<int> vec,int n)//经典的最长上升子序列问题，当然还可用二分优化
    {
        vector<int> dp(n,0);
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(vec[i]>vec[j])
                    dp[i]=max(dp[i],dp[j]);
            }
            dp[i]++;
        }
        return *max_element(dp.begin(),dp.end());
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//排序
        vector<int> height;
        for(int i=0;i<n;i++)
        {
            height.push_back(letters[i][1]);
        }
        int res=LIS(height,n);//按照高度最长上升子序列
        return  res;
    }
};

今天 02:23:11 回复(0)