> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/longest-increasing-subsequence/russian-doll-envelopes.md).

# Russian Doll Envelopes

<https://leetcode.com/problems/russian-doll-envelopes/description/>

> 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)
>
> **Example:**\
> Given envelopes =`[[5,4],[6,4],[6,7],[2,3]]`, the maximum number of envelopes you can Russian doll is`3`(\[2,3] => \[5,4] => \[6,7]).

## Thoughts

给定一堆pair，要求找出满足pair-wise递增最长序列。一维的知道怎么做，现在要用一维的思想解决二维的。直接套用一维LIS把元素做pair-wise比较是很麻烦的，比如\[(1, 1), (2,3),(3,2),(3,4)] ，对长度为2的LIS要同时保留(2, 3)和(3, 2)才能保证后面的结果正确。 换个思路，先对它们其中一个值(比如宽)进行排序, 那么每个元素都比前一个元素的宽大了。 如果排序遇到宽相等情况, 把高更大的排在前面, 能避免在下一步里把等宽的放进序列里。接着针对剩下的元素, 直接用一维LIS解决，这样能保证找出来的LIS满足高和宽都是递增的。&#x20;

针对一维LIS问题，除了O(N^2)的DP解法，还有O(NlgN)的二分法。

## Code

```cpp
/*
 * @lc app=leetcode id=354 lang=cpp
 *
 * [354] Russian Doll Envelopes
 */
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        vector<int> tails;
        for (const auto &e : envelopes) {
            auto iter = lower_bound(tails.begin(), tails.end(), e[1]);
            if (iter == tails.end()) {
                tails.push_back(e[1]);
            } else {
                *iter = e[1];
            }
        }
        return tails.size();
    }
};

```

```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = envelopes.length, end = 0;
        if (n == 0) {
            return 0;
        }
        int[] tails = new int[n];
        for (int i = 0; i < n; i++) {
            int pos = lowerBound(tails, envelopes[i][1], end);
            tails[pos] = envelopes[i][1];
            if (pos == end) {
                end++;
            }
        }

        return end;
    }

    private int lowerBound(int[] tails, int target, int end) {
        int start = 0;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (tails[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}
```

## Analysis

时间复杂度O(NlgN). 空间O(N).