题目转化

首先将题目数据按照(W, L)排序。
如果(W1, L1) < (W2, L2)，再加上题目给的W <= L条件，则(W2, L2)只能被放在(W1, L1)下面。
如果(W1, L1) = (W2, L2)，两个积木完全相等，先后顺序没有限制，在不影响答案正确性的情况下，可以自己加上限制，排序之后排在后面的被放在下面。

这样，排在后面的积木一定被放在下方，则每种可能搭成的塔对应排序后的积木序列的一个子序列。这样，最高能够搭成的塔的层数等于L值的最长非降子序列的长度。

求解最长非降子序列

方法一、长度数组+二分

构建长度数组A。A[k]表示长度为k的非降序列的最小结尾数值。
在考虑积木(W, L)时，只要A[k] <= L就可以在A[k]所代表的非降序列之后加上L值，构成长度增加1的新非降序列。
此处很重要的一点就是发现A数组本身就是非降的。因为如果存在一个长度为k的序列以A[k]结尾，则必定存在一个长度为k-1且以A[k]结尾的序列，于是A[k-1] <= A[k]成立。
有了这个结论，可以用二分法找到使得A[k]<=L的最大k值，并构建出长度为k+1的新序列,然后更新A数组。
时间复杂度O(NlogN)

代码

class Solution1{
    public:
        int maxBlock(vector<pair<int,int>> Blocks){
            int N = Blocks.size();
            sort(Blocks.begin(), Blocks.end());

            //A[i]表示长度为i的所有块序列中，最底下的一块的y值的最小值
            //根据定义，A数组是单调非降的， A[0]=0是空序列
            vector<int> A(1, 0);
            for(int i = 0 ; i < N ; ++i){
                //考虑积木(W，L)
                //二分法找出最大的k，使得 A[k] <= L
                int k = upper_bound(A.begin(), A.end(), Blocks[i].second) - A.begin() - 1;
                //构建出长度为k+1的新数组
                int newLen = k + 1;

                //用当前数组更新A数组
                if(A.size() < newLen + 1){
                    A.push_back(Blocks[i].second);
                }
                else{
                    A[newLen] = min(A[newLen], Blocks[i].second);
                }
            }
            //A数组包含A[0]，所以最长序列长度为A.size()-1
            return A.size() - 1;
        }
};

方法二、离散化+树状数组

构建数组A[i]表示以积木i为底最高搭多少层。
从左到右扫描到积木(W[i],L[i])的时候，A[i] = max(A[k]) + 1，其中k < i且L[k] <= L[i]。于是，需要一个数据结构，可以存储(L[k], A[k])并且支持快速查找L[k] < L[i]时A[k]的最大值。

首先是离散化，将所有L值有序地映射到自然数Lid。
然后构建数组B。B[Lid[k]]为L[k]对应的最大A[k]。
对于数组B我们需要两个操作。
第一是加入数据(Lid[k], A[k])。即B[Lid[k]] = max(B[Lid[k]], A[k])。这是点修改。
第二是求所有Lid[k] <= Lid[i]的值中的最大值，即求B数组中从1到Lid[i]这些值中的最大值。这是区间查询。

点修改+区间查询，可以使用树状数组或者线段树实现。
时间复杂度O(NlogN)

代码

class Solution2{
    // 离散化结构，将所有L值映射到自然数
    int N, Rn;
    vector<int> Rank;
    void initRank(vector<pair<int,int>> &Blocks){
        Rank.resize(N);
        for(int i = 0 ; i < N ; ++i)
            Rank[i] = Blocks[i].second;

        sort(Rank.begin(), Rank.end());
    }
    int getRank(int V){
        //找到V值第一次出现的下标，保证V值出现在Rank中
        return lower_bound(Rank.begin(), Rank.end(), V) - Rank.begin();
    }

    //树状数组结构，下标从1开始
    vector<int> Max;
    void initBIT(){
        Max = vector<int>(N+2, 0);
    }
    void Add(int X, int V){
        while(X <= N){
            Max[X] = max(Max[X], V);
            X += X & -X;
        }
    }
    int Query(int X){
        int maxLen = 0;
        while(X > 0){
            maxLen = max(maxLen, Max[X]);
            X -= X & -X;
        }
        return maxLen;
    }

    public:
        int maxBlock(vector<pair<int,int>> Blocks){
            N = Blocks.size();
            sort(Blocks.begin(), Blocks.end());

            initRank(Blocks);//离散化的初始化
            initBIT();//树状数组的初始化

            for(int i = 0 ; i < N ; ++i){
                //考虑积木(W, L)
                //求出L映射到的自然数之后再+1的值，因为树状数组是从1开始的
                int Lid = getRank(Blocks[i].second) + 1;
                //求以当前积木为底的最大层数
                //Query(Lid)求出了所有 Lid[k] <= Lid[i](即L[k] <= L[i]) 对应的答案中的最大值
                int cntLen = Query(Lid) + 1;
                //用以Blocks[i]结尾的最长序列更新树状数组的数据
                Add(Lid, cntLen);
            }
            //Query(N)求出以每个积木为底的最大层数中的最大值
            return Query(N);
        }
};