LeetCode 354 俄罗斯套娃信封问题

这道题给出的是信封的长度和宽度，只有一个信封长度和宽度都比一个信封小时，才能将这个小的信封放入大的信封里，问最多可以嵌套放多少个信封，信封不可以旋转。这道题和之前做过的一个嵌套矩形很像，不过那个可以旋转，用DAG上的动态规划就可以做，这道题我开始也是用同样的方法，但是不行，时间复杂度O(n2)，会超时。后来看了解题思路才突然想到方法，首先将信封排序，先按w升序排，然后按h降序排，这样的目的是能保证只要后面的信封h比前面大，就能把前面的信封放到后面的信封中，而且防止同w的信封嵌套。维护一个数组保存长度最大为len时的信封宽度，做到这里其实就是最长上升子序列问题了。最长上升子序列的做法可以看这里————最长上升子自序列。这种方法的时间复杂度为O(nlogn)，可以通过。

class Solution {
public:
    static bool cmp (vector a,vector b)
    {
        return a[0]b[1]);
    }
    int maxEnvelopes(vector>& envelopes) {
        int sz=envelopes.size();
        int dp[sz+1],len=0;
        sort(envelopes.begin(),envelopes.end(),cmp);
        dp[0]=0;
        for(int i=0;idp[len])
            {
                len++;
                dp[len]=envelopes[i][1];
            }
            else
            {
                int l=0,r=len,mid;
                while(l<=r)
                {
                    mid=(l+r)/2;
                    if(dp[mid]