LeetCode系列354—俄罗斯套娃信封问题

题意

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

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

说明：不允许旋转信封。

示例：

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

题解

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if(n == 0) return 0;
        // 将信封按照w递增，h递减，w优先排序
        sort(envelopes.begin(), envelopes.end(), cmp);
        vector<int> heights(n);
        for(int i=0;i<n;i++){
            heights[i] = envelopes[i][1];
        }
        return lengthOfLIS(heights);
    }

    static bool cmp(vector<int> a, vector<int> b){
        if(a[0] < b[0]) return true;
        else if(a[0] == b[0] && a[1] > b[1]) return true;
        else return false;
    }

    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; 
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else{
						r = mid - 1;
					} 
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }

};
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46