算法设计与分析-Week16

发表于

Russian Doll Envelopes

题目描述

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Note:
Rotation is not allowed.

Example 1:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

解题思路

本题实为俄罗斯套娃问题，给定一组拥有高和宽的信封，当一个信封的高和宽都大于另一个信封时，可将另一个信封装入该信封，层层嵌套，求最大的嵌套数。
由于必须高宽都满足大于的条件，因此可先对数组的其中一维进行排序，如对宽进行排序，然后可仅考虑高，用最长递增子序列可得到问题的解。在对宽进行排序时，若宽相等则高大的要放在前面，如[3, 4]要放在[3, 3]前面，因为此时[3, 3]是不能套进[3, 4]的，若[3, 3]放在前面会影响后面最长递增子序列的计算。
最长递增子序列：
用一个数组arr，arr[i]表示以i结尾的最长递增子序列的长度，初始化arr[0] = 1，要求arr[i]，需要比较i和前面所有的元素j，若信封i的高大于信封j的高且arr[j] + 1 > arr[i]，则更新arr[i]为arr[j] + 1。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](pair<int, int> a, pair<int, int> b){
            if(a.first < b.first) return true;
            if(a.first == b.first && a.second >= b.second) return true;
            return false;
        });
        int maxEnvelopes = 1;
        int n = envelopes.size();
        if(n == 0) return 0;
        vector<int> arr(n, 0);
        arr[0] = 1;
        for(int i = 1; i < n; i++) {
            arr[i] = 1;
            for(int j = 0; j < i; j++) {
                if(envelopes[j].second < envelopes[i].second && arr[j] + 1 > arr[i]) {
                    arr[i] = arr[j] + 1;
                }
            }
            if(arr[i] > maxEnvelopes) maxEnvelopes = arr[i];
        }
        return maxEnvelopes;
    }
};
0%