题目描述

给你一个二维整数数组 envelopes，其中 envelopes[i] = [w_i, h_i]，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

样例

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

限制

• 1 <= envelopes.length <= 10^5
• envelopes[i].length == 2
• 1 <= w_i, h_i <= 10^5

算法1

(动态规划 + 树状数组) $O(n \log n)$

1. 按照第一维从小到大排序，将第二维离散化。
2. 设状态 $f(i)$ 表示以第 $i$ 个信封为结尾的最大上升子序列的长度。
3. 假设我们能快速找到一个 $j < i$，满足 e[j][0] < e[i][0] 并且 e[j][1] < e[i][1]，则转移 $f(i) = \max (f(j) + 1)$。由于我们已经排过序，所以满足 e[j][0] < e[i][0] 的 $j$ 的范围很好找，但暴力做的话，第二维就需要枚举所有可能的 $j$。此时我们用树状数组来替代枚举的过程。
4. 用树状数组维护在第二维数域上的前缀最大值，每次我们寻找第二维 [1, e[i][1] - 1] 这个区间中的最大值，并获取这个值然后加 1。更新时，将当前这个位置的动规值更新到 e[i][1] 上。
5. 最终答案为 $\max(f(i))$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 动态规划的状态数为 $O(n)$，每次转移需要操作树状数组，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间离散化，存储树状数组和动规值。

C++ 代码

class Solution {
public:
    vector<int> bits;
    int m;

    void update(int x, int y) {
        for (; x <= m; x += x & -x)
            bits[x] = max(bits[x], y);
    }

    int query(int x) {
        int tot = 0;
        for (; x; x -= x & -x)
            tot = max(tot, bits[x]);

        return tot;
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end());

        vector<int> a(n);
        for (int i = 0; i < n; i++)
            a[i] = envelopes[i][1];

        sort(a.begin(), a.end());
        m = unique(a.begin(), a.end()) - a.begin();
        a.resize(m);

        for (int i = 0; i < n; i++)
            envelopes[i][1] = lower_bound(a.begin(), a.end(), envelopes[i][1])
                                - a.begin() + 1;

        bits.resize(m + 1, 0);

        vector<int> f(n);
        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (envelopes[i][0] != envelopes[j][0]) {
                while (j < i) {
                    update(envelopes[j][1], f[j]);
                    j++;
                }
            }
            f[i] = query(envelopes[i][1] - 1) + 1;
            ans = max(ans, f[i]);
        }

        return ans;
    }
};

算法2

(动态规划，二分) $O(n \log n)$

1. 按照第一维从小到大排序。
2. 仍然是动态规划的思路，但这次使用二分求转移。
3. 除 $f$ 数组外，我们额外维护一个 $g$ 数组，其中 $g(v)$ 表示长度为 $v$ 的最长上升子序列的最小的结尾数字。
4. 容易证明 $g$ 是单调递增的，即 $v_1 < v_2$，则 $g(v_1) < g(v_2)$。
5. 我们每次二分查找 $g$ 数组，找到最小的 $v$ 满足 $g(v) >= envelopes[i][1]$，然后令 $f(i) = v $。更新时，维护 $g(f(i)) = min(g(f(i)), envelopes[i][1])$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 动态规划的状态数为 $O(n)$，每次转移需要操作需要 $O(\log n)$ 的时间二分，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 $f$ 和 $g$ 数组，

C++ 代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end());

        vector<int> f(n), g;
        g.push_back(0);

        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (envelopes[i][0] != envelopes[j][0]) {
                while (j < i) {
                    if (f[j] == g.size())
                        g.push_back(envelopes[j][1]);
                    else
                        g[f[j]] = min(g[f[j]], envelopes[j][1]);
                    j++;
                }
            }

            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >> 1;
                if (envelopes[i][1] <= g[mid])
                    r = mid;
                else
                    l = mid + 1;
            }

            f[i] = l;
            ans = max(ans, f[i]);
        }

        return ans;
    }
};