# Russian Doll Envelopes

### 问题描述​

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[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]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

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

### 分析​

• 首先，对宽度w从小到大排序，确保了w这个维度可以嵌套，接下来只需要专注高度h这个维度能否嵌套。
• 其次，两个w相同的信封不能嵌套（因为题目说了长宽相同也无法嵌套），所以对于宽度w相同的信封，按照高度h进行降序排序，确保了LIS 中不存在多个w相同的信封。

### 代码​

#### 动规​

// Russian Doll Envelopes// Time Complexity: O(N^2)// Space Complexity: O(N)// This version will TLEclass Solution {public:    int maxEnvelopes(vector<vector<int>>& envelopes) {        std::sort(envelopes.begin(), envelopes.end(), compare);        vector<int> heights(envelopes.size());        for (int i = 0; i < envelopes.size(); i++) {            heights[i] = envelopes[i][1];        }        return lengthOfLIS(heights);    }private:    // sort by width in ascending order, while sort by height in descending order    bool static compare(const vector<int>& envelope1, const vector<int>& envelope2) {        if (envelope1[0] == envelope2[0]) {            return envelope1[1] > envelope2[1];        } else {            return envelope1[0] < envelope2[0];        }    }    int static lengthOfLIS(vector<int>& nums) {        if (nums.empty()) return 0;        vector<int> dp(nums.size(), 1);        for (int j = 1; j < nums.size(); ++j) {            for (int i = 0; i < j; ++i) {                if (nums[i] < nums[j]) {                    dp[j] = max(dp[j], dp[i] + 1);                }            }        }        return *std::max_element(dp.begin(), dp.end());    }};

#### 二分查找​

// Russian Doll Envelopes// Time Complexity: O(NlogN)// Space Complexity: O(N)class Solution {public:    int maxEnvelopes(vector<vector<int>>& envelopes) {        std::sort(envelopes.begin(), envelopes.end(), compare);        vector<int> heights(envelopes.size());        for (int i = 0; i < envelopes.size(); i++) {            heights[i] = envelopes[i][1];        }        return lengthOfLIS(heights);    }private:    // sort by width in ascending order, while sort by height in descending order    bool static compare(const vector<int>& envelope1, const vector<int>& envelope2) {        if (envelope1[0] == envelope2[0]) {            return envelope1[1] > envelope2[1];        } else {            return envelope1[0] < envelope2[0];        }    }    int lengthOfLIS(vector<int>& nums) {        vector<int> lis;        for (auto x : nums) {            int insertPos = lower_bound(lis, 0, lis.size(), x);            if (insertPos >= lis.size()) {                lis.push_back(x);            } else {                lis[insertPos] = x;            }        }        return lis.size();    }    int lower_bound (const vector<int>& A, int first, int last, int target) {        while (first != last) {            int mid = first + (last - first) / 2;            if (target > A[mid]) first = ++mid;            else                 last = mid;        }        return first;    }};