最长上升子序列问题LIS

最长上升子序列问题是一个比较重要的算法问题，建议掌握。

面试题 17.08. 马戏团人塔

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
提示：
height.length == weight.length <= 10000

这里先使用sort根据height从小到大排序，其中关键的是如果height相同则按照weight从大到小排序（注意一个是从小到大，一个是从大到小）。
这样安排是为了让后续的根据weight求最大上升子序列时不会选到height一样的数据，即让height相同的数据的weight从大到小排列，让它不满足上升序列的“上升”，这样就巧妙避开了重复选取，将身高相同的人看成1个集合。
最后就是根据weight值求最长上升子序列的长度，即leetcode300的方法。这里使用了STL函数lower_bound()代替二分查找来简化代码。

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字。
在从大到小的排序数组中，
lower_bound( begin,end,num,greater<type>() ):二分查找第一个小于或等于num的数字。
upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字。

class Solution {
public:
    static bool cmp(pair<int,int> a,pair<int,int> b)
    {
        if(a.first<b.first)
        return true;
        else if(a.first==b.first)
        return a.second>b.second;
        return false;
    }

    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        int l=height.size();
        if(l==0)
        return 0;
        vector<pair<int,int>> pep;
        vector<int> tails;
        for(int i=0;i<l;i++)
        {
            pep.push_back({height[i],weight[i]});
        }
        sort(pep.begin(),pep.end(),cmp);
        for(auto p:pep)
        {
            if(tails.empty()||p.second>tails.back())
            tails.push_back(p.second);
            else 
            {
                auto pos=lower_bound(tails.begin(),tails.end(),p.second);
                *pos=p.second;
            }
        }
        return tails.size();
    }
};

要注意的是，自定义比较函数如果在类中，应该定义为static，因为：sort中调用函数cmp，不用加对象名，就能直接访问函数。

354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
不允许旋转信封。
示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b)
    {
        if(a[0]<b[0]) return true;
        else if(a[0] == b[0]) return a[1] > b[1];
        return false;
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n=envelopes.size();
        sort(envelopes.begin(),envelopes.end(), cmp);
        vector<int> t;
        for(int i=0;i<n;i++)
        {
            if(t.empty()||t.back()<envelopes[i][1])
            t.push_back(envelopes[i][1]);
            else
            {
                auto pos=lower_bound(t.begin(),t.end(),envelopes[i][1]);
                *pos=envelopes[i][1];
            }
        }
        return t.size();
    }
};

二维数组的sort问题；&和，&是取地址，是是指针，向指定地址进行操作。

最长上升子序列问题LIS