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();
    }
};

Link

LeetCode-354 Russian Doll Envelopes