信封嵌套问题

C++ 解法, 执行用时: 4ms, 内存消耗: 536KB, 提交时间: 2021-04-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        int n=letters.size();
        if(n<2)
            return n;
        vector<int> indexVec(n,0);
        for(int i=0;i<n;++i)
            indexVec[i]=i;
        sort(indexVec.begin(),indexVec.end(),[&letters](int index1,int index2)
        {
           if(letters[index1][0]!=letters[index2][0])
               return letters[index1][0]<letters[index2][0];
           else
               return letters[index1][1]>letters[index2][1];
        });
        //相同的 后面绝对不可能是个上升序列
        vector<int> hVec(n,0);
        for(int i=0;i<n;++i)
        {
            hVec[i]=letters[indexVec[i]][1];
        }
        vector<int> tail;
        tail.emplace_back(hVec[0]);
        for(int i=1;i<n;++i)
        {
            int index=lower_bound(tail.begin(),tail.end(),hVec[i])-tail.begin();
            if(index==tail.size())
                tail.emplace_back(hVec[i]);
            else
            {
                if(hVec[i]<tail[index])
                    tail[index]=hVec[i];
            }
        }
        return tail.size();
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 560KB, 提交时间: 2022-07-26

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        vector<vector<int> >& v = letters;
        sort(v.begin(),v.end(),[](vector<int>&a,vector<int>&b){
            if(a[0]==b[0])return a[1]>b[1];else return a[0]<b[0];
        });
    
        int n = v.size();
        vector<int> t(n);
        for(int i=0;i<n;i++)t[i]= v[i][1];
        
        auto end = t.begin();
        for(int i=0;i<n;i++)
        {
            auto cur = lower_bound(t.begin(), end, t[i]);
            *cur = t[i];
            if(cur==end)
            {
                end++;
            }
        }
        return end - t.begin();
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 560KB, 提交时间: 2022-04-04

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int n = letters.size();
        vector<int> f(n + 1, 0);
        sort(letters.begin(), letters.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || a[0] == b[0] && a[1] > b[1];
            });
        vector<pair<int, int> > saves;
        for (int i = 0; i < n; ++i) {
            auto t = make_pair(letters[i][0], letters[i][1]);
            int idx = lower_bound(saves.begin(), saves.end(), t,
                [](const pair<int, int>& a, const pair<int, int>& b) {
                    return a.first < b.first && a.second < b.second;
                }) - saves.begin();
            if (idx >= saves.size()) {
                saves.push_back(t);
                continue;
            }
            saves[idx] = t;
        }
        return saves.size();
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 532KB, 提交时间: 2021-10-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int len = letters.size();
        if(len < 2) return len;
        
        sort(letters.begin(), letters.end(), 
             [](const auto &lhs, const auto &rhs){
                 return lhs[0]<rhs[0] || lhs[0]==rhs[0]&&lhs[1]>rhs[1];
             });
        vector<int> record( {letters[0][1]} );
        int idx = 0, H, left, mid, right;
        for(int i=1; i<len; i++){
            if((H = letters[i][1]) > record[idx])
                { record.push_back(H);   idx++;   continue; }
            auto loc=lower_bound(record.begin(), record.end(), H );
            *loc=H;
        }
        return idx+1;
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 536KB, 提交时间: 2021-08-05

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int len = letters.size();
        if(len < 2) return len;
        
        sort(letters.begin(), letters.end(), 
             [](const auto &lhs, const auto &rhs){
                 return lhs[0]<rhs[0] || lhs[0]==rhs[0]&&lhs[1]>rhs[1];
             });
        vector<int> record( {letters[0][1]} );
        int idx = 0, H, left, mid, right;
        for(int i=1; i<len; i++){
            if((H = letters[i][1]) > record[idx])
                { record.push_back(H);   idx++;   continue; }
//             left = 0;   right = idx;
//             while(left <= right)
//             {
//                 mid = left+right >>1;
//                 record[mid] < H ? (left = mid+1) : (right = mid-1);
//             }
            auto loc=lower_bound(record.begin(), record.end(), H );
            *loc=H;
        }
        return idx+1;
    }
};

详情