Description

俄罗斯套信封问题,给定\(n\)封信,每一封信\(i\)有长宽\(h_i, w_i\),每一封信嵌套要求长宽均满足严格递增关系,问最多能嵌套多少封信

Constraints

时间复杂度不超过\(O(nlogn)\)

Solution

二维LIS,使用排序降低维度,后面就是LIS模板

\(O(nlogn)\)的LIS忘记怎么写了,翻了下书

它的定义是比较特殊的:设\(dp[i]\)为长度为\(i+1\)的上升子序列中末尾元素的最小值

Code

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        auto &es = envelopes;
        // Note: b[1] < a[1],这样避免第一维相同时选了递增的二维
        sort(es.begin(), es.end(), [](auto &a, auto &b) {
            return tie(a[0], b[1]) < tie(b[0], a[1]);
        });
        constexpr int INF = 1<<30;
        vector<int> dp(es.size(), INF);
        for(auto &e : es) {
            *lower_bound(dp.begin(), dp.end(), e[1]) = e[1];
        }
        return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    }
};

LeetCode-354 Russian Doll Envelopes