The rules for patient sorting

其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关,甚至有一种排序方法就叫做 patience sorting（耐心排序,复杂度为$nlogn$）.And the essence of this sort is by二分查找实现的.
其规则为：
1、Draw cards in turn、Press the card,But you can only push a lower-ranked card over a higher-ranked card.
2、如果当前牌点数较大没有可以放置的堆,则新建一个堆,把这张牌放进去.
3、如果当前牌有多个堆可供选择,则选择最左边的那一堆放置.
按照上述规则执行,可以算出最长递增子序列,牌的堆数就是最长递增子序列的长度.其中,The implementation of the third rule is used寻找左侧边界的二分查找！

Implementation of patient sorting

class Solution {
    
public:
    int lengthOfLIS(vector<int>& nums) {
    
        int n = nums.size();
        //Build a deck first
        vector<int>top(n);
        //Record the number of decks
        int ans = 0;
        //Start placing each card
        for(int i=0;i<n;++i)
        {
    
            int card = nums[i];
            //The first deck and the last deck
            int left = 0,right = ans-1;
            while(left <= right)
            {
    
                int mid = left+(right-left)/2;
                //The condition is satisfied if the current card is less than the top of the card
                if(card <= top[mid]) right = mid-1;
                else left = mid+1;
            }
            if(left == ans) ++ans;//Equivalent to lookup beyond bounds
            //Put in cards
            top[left] = card;
        }
        return ans;
    }
};

The largest increasing subsequence in two dimensions

先对宽度 w 进行升序排序,如果遇到 w 相同的情况,则按照高度 h 降序排序(This is because of a widthwOnly one envelope can exist,So simply will be the largesth的排在最前面,i.e. so you can focus onh,And don't worry about selecting more than onew相同的信封);之后把所有的 h 作为一个数组,在这个数组上计算 LIS 的长度就是答案.

class Solution {
    
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
    
        int n = envelopes.size();
        sort(envelopes.begin(),envelopes.end(),[](vector<int> &a,vector<int>& b){
    return a[0]==b[0]?
        a[1]>b[1]:a[0]<b[0];});
        //The following is the order of patience！
        vector<int>top(n,0);
        int ans = 0; 
        for(int i=0;i<n;++i)
        {
    
            int card = envelopes[i][1];
            int left = 0,right = ans-1;
            while(left<=right)
            {
    
                int mid = left+(right-left)/2;
                if(card<=top[mid])  right = mid-1;
                else left = mid+1;
            }
            if(left == ans) ++ans;
            top[left] = card;
        }
        return ans;
    }
};