每日一题354

354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

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

说明:
不允许旋转信封。

思路

  • 先对数组按递增排序
  • dp数组的每个元素表示到当前位置的俄罗斯套娃的个数
  • i从1到n-1, j从0到i-1依次比较
  • 时间复杂度o(n2),空间复杂度o(n)
class Solution {
public:
    static bool minval(vector<int> &r1, vector<int> &r2) {
        return r1[0] < r2[0] || r1[0] == r2[0] && r1[1] < r2[1]; //按照递增排序,0相等的时候比较1
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if (n < 2) {
            return n;
        }
        sort(envelopes.begin(), envelopes.end(), minval);

        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);//dp[i]表示以i结尾的满足俄罗斯套娃的个数
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

思路2

  • 二分法,减少比较次数
  • 时间复杂度o(nlgn)
  • 空间复杂度o(n)
class Solution {
public:
    static bool minval(vector<int> &r1, vector<int> &r2) {
        return r1[0] < r2[0] || (r1[0] == r2[0] && r1[1] > r2[1]);
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if (n < 2) {
            return n;
        }
        sort(envelopes.begin(), envelopes.end(), minval);

        vector<int> f = {envelopes[0][1]};
        for (int i = 1; i < n; ++i) {
            int num = envelopes[i][1];
            if (num > f.back()) {
                f.push_back(num);
            } else {
                auto it = lower_bound(f.begin(), f.end(), num);//如果没有找到,指向初始位置
                *it = num;
            }
        }
        return f.size();
    }
};

评论

暂无评论