solution.md

# 俄罗斯套娃信封问题

<p>给你一个二维整数数组 <code>envelopes</code> ，其中 <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> ，表示第 <code>i</code> 个信封的宽度和高度。</p>

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

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

<p><strong>注意</strong>：不允许旋转信封。</p>
 

<p><strong>示例 1：</strong></p>

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

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>envelopes = [[1,1],[1,1],[1,1]]
<strong>输出：</strong>1
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= envelopes.length <= 5000</code></li>
	<li><code>envelopes[i].length == 2</code></li>
	<li><code>1 <= w<sub>i</sub>, h<sub>i</sub> <= 10<sup>4</sup></code></li>
</ul>

<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    static bool myCmp(pair<int, int> &one, pair<int, int> &two)
    {
        if (one.first == two.first)
        {
            return one.second <= two.second;
        }
        else
        {
            return one.first <= two.first;
        }
    }
    int maxEnvelopes(vector<pair<int, int>> &envelopes)
    {
        int result = 1;
        int envelopesSize = envelopes.size();
        if (envelopesSize == 0)
        {
            return 0;
        }
        vector<int> dp(envelopesSize, 1);
        sort(envelopes.begin(), envelopes.end(), myCmp);

        for (int beginIndex = 1; beginIndex < envelopesSize; ++beginIndex)
        {
            for (int scanIndex = 0; scanIndex < beginIndex; ++scanIndex)
            {
                if (envelopes[scanIndex].first <= envelopes[beginIndex].first)
                {

                    dp[beginIndex] = max(dp[beginIndex], dp[scanIndex]);
                }
            }
            result = max(result, dp[beginIndex]);
        }
        return result;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), [](const vector<int> &a, const vector<int> &b)
             { return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]; });
        vector<int> dp;
        for (const auto &e : envelopes)
        {
            auto p = lower_bound(dp.begin(), dp.end(), e[1]);
            if (p == dp.end())
                dp.push_back(e[1]);
            else
                *p = e[1];
        }
        return dp.size();
    }
};
```

### B

```cpp
class Solution
{
public:
    static bool judge(const pair<int, int> a, const pair<int, int> b)
    {
        if (a.first != b.first)
        {
            return a.first < b.first;
        }
        return a.second > b.second;
    }
    int get_cur_index(int *dp, int index, int value)
    {
        int left = 1;
        int right = index;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (value < dp[mid])
            {
                right = mid;
            }
            else if (value > dp[mid])
            {
                left = mid + 1;
            }
            else if (value == dp[mid])
            {
                return mid;
            }
        }
        return left;
    }
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        if (envelopes.empty())
        {
            return 0;
        }
        vector<pair<int, int>> nums;
        for (int i = 0; i < envelopes.size(); i++)
        {
            nums.push_back(make_pair(envelopes[i][0], envelopes[i][1]));
        }
        sort(nums.begin(), nums.end(), this->judge);
        int dp[envelopes.size() + 1];
        dp[1] = nums[0].second;
        int index = 1;

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i].second > dp[index])
            {
                dp[++index] = nums[i].second;
            }
            else
            {
                int new_index = get_cur_index(dp, index, nums[i].second);
                dp[new_index] = nums[i].second;
            }
        }
        return index;
    }
};
```

### C

```cpp
bool sortV(vector<int> &a, vector<int> &b)
{
    if (a[0] == b[0])
        return a[1] > b[1];
    else
        return a[0] < b[0];
}
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        if (envelopes.empty())
            return 0;
        sort(envelopes.begin(), envelopes.end(), sortV);
        int n = envelopes.size();
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 1; i < envelopes.size(); i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (envelopes[i][1] > envelopes[j][1])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
```