单调栈 O(N)

两次遍历

创建一个栈来存各个值的下标。
从左往右扫描数组，在将A[i]加入栈之前，将所有大于等于A[i]的元素出栈，此时栈顶元素就是左侧第一个小于A[i]的数的下标，在记录答案之后将i入栈，继续向右扫描。
在此操作下，栈中元素一直保持单调递增，故称单调栈。

正确性证明：假设j < i是i左侧第一个满足A[j] < A[i]的数。
由假设可得，对于每个k(j < k < i)，都有A[k] >= A[i]，否则与假设矛盾。
这些数都会被i出栈，出栈之后栈顶元素就是j。

同理从右往左扫描即可求出右侧第一个小于A[i]的数的下标。
共遍历数据两次，每个下标最多入栈两次出栈两次，时间复杂度O(N)。

一次遍历

如果注意到下面这个性质，就可以优化到一次遍历求出答案。
此时算法改为从左到右扫描，每个i将大于A[i]的下标出栈，而不是大于等于。

性质：每个数都被其右侧第一个小于它的数出栈。
假设j>i是i右侧第一个满足A[j] < A[i]的数，则根据算法，j在加入栈之前一定会将i出栈(1)。根据定义，所有的k(i < k < j)都满足A[k] >= A[i]，否则与假设矛盾。于是这些k都不可能将i出栈(2)。由(1)和(2)可得，i被j出栈，于是在i出栈之前，记录j为i右侧第一个满足A[j] < A[i]的下标。

这样做唯一的问题就是重复值问题，在j将大于A[j]的下标都出栈之后，栈顶元素可能与j相同，此时需要做特殊处理。注意到此时栈顶元素已经被扫描过，于是其左侧第一个小于它的元素下标已经知道，只需要复制其答案即可，详见代码。

每个下标入栈一次，出栈一次，入栈前计算左侧答案，出栈前计算右侧答案。
时间复杂度O(N)

莫队算法（根号N分解） O(NsqrtN)

令 D = sqrt(N)。
将N个数分成D组，每组D个数，并求出每组的最小值。
此时，以R结尾的区间可表示为 连续完整分组加上包含R的分组的一部分
在查询最小值的时候，首先遍历当前分组（最多D个数），再向左找到第一个最小值小于A[R]的分组，此时答案一定在此分组之内（最多D个分组）。最后在这个分组内查找小于A[R]的数（最多D个数）。右侧同理。

这样，单次查询复杂度为O(sqrtN)。
一共2N次查询，总时间复杂度O(NsqrtN)。

线段树 O(NlogN)

建一颗线段树，每个结点存对应区间的最小值，直接查找i左右第一个小于A[i]的数即可。
每次查询是O(logN)，共有2N次查询，总复杂度O(NlogN)。

代码

单调栈两次遍历

vector<vector<int>> findNearestLessThan(vector<int> &A){
    int N = A.size();
    // L[i] : i的左侧第一个小于A[i]的数的下标
    // R[i] : i的右侧第一个小于A[i]的数的下标
    vector<int> L(N), R(N);
    stack<int> S;

    // 先求L，从左往右扫描
    for(int i = 0 ; i < N ; ++i){
        // 删除 >= A[i] 的所有下标
        while(!S.empty() && 
              A[S.top()] >= A[i]){
            S.pop();
        }
        // 此时栈顶元素就是左侧第一个小于A[i]的数的下标
        L[i] = S.empty() ? -1
                         : S.top();
        // 将 i 入栈
        S.push(i);
    }
    // 清空栈中元素
    while(!S.empty())
        S.pop();

    // 再求R， 从右往左扫描
    for(int i = N - 1 ; i >= 0 ; --i){
        // 删除 >= A[i] 的所有下标
        while(!S.empty() && 
               A[S.top()] >= A[i]){
            S.pop();
        }
        // 此时栈顶元素就是右侧第一个小于A[i]的数的下标
        R[i] = S.empty() ? -1
                         : S.top();
        S.push(i);
    }
    return {L, R};
}

单调栈一次遍历

vector<vector<int>> findNearestLessThan(vector<int> &A){
    int N = A.size();
    // L[i] : i的左侧第一个小于A[i]的数的下标
    // R[i] : i的右侧第一个小于A[i]的数的下标
    vector<int> L(N), R(N);

    stack<int> S;

    for(int i = 0 ; i <= N ; ++i){
        // 删除 > A[i] 的所有下标
        // 特殊处理：i = N 时将所有元素都退栈
        while(!S.empty() && 
              (i == N || A[S.top()] > A[i])){
            // 将栈顶元素退栈时，A[i]是其右侧第一个小于它的值
            // i = N 时其右侧无小于它的值
            R[S.top()] = i < N ? i : -1;
            // 将栈顶元素退栈
            S.pop();
        }

        // 如果空栈，赋值-1
        // 否则，栈顶元素小于等于A[i]
        // 如果等于，复制其答案
        // 如果小于，取其下标
        L[i] = S.empty() ? -1
                         : A[S.top()] == A[i] ? L[S.top()]
                                              : S.top();
        // 将i入栈
        S.push(i);
    }
    return {L, R};
}

莫队算法

class Solution_Mo{
    int groupNum, groupSize;
    vector<int> Min;
    void Init(vector<int> &A, int N){
        // 将A分成根号N组
        groupSize = (int) ceil(sqrt(N));
        groupNum = N / groupSize + 1;
        Min = vector<int>(groupNum, INT_MAX);

        // 计算每组最小值
        for(int i = 0 ; i < N ; ++i){
            // 求分组ID
            int groupID = i / groupSize;
            // 更新分组最小值
            Min[groupID] = min(Min[groupID], A[i]);
        }
    }
    int FindLeftLT(vector<int> &A, int I){
        // 查找I所属分组
        int groupID = I / groupSize;

        // 查询当前分组中I的左侧的值
        int start = groupID * groupSize;
        for(int i = I - 1 ; i >= start ; --i){
            if(A[i] < A[I])
                return i;
        }
        // 向左找到第一个存在 < A[I]的值的分组
        for(int i = groupID - 1 ; i >= 0 ; --i){
            if(Min[i] < A[I]){
                // 定位组内元素, 本组下标范围：[i * groupSize, (i+1) * groupSize)
                int start = i * groupSize;
                int end = min((i+1)*groupSize, (int)A.size());

                for(int j = end - 1 ; j >= start ; --j){
                    if(A[j] < A[I])
                        return j;
                }
            }
        }
        // 找不到
        return -1;
    }
    int FindRightLT(vector<int> &A, int I){
        int groupID = I / groupSize;

        // 查询当前分组中I的右侧的值
        int end = min((groupID + 1) * groupSize, (int)A.size());
        for(int i = I + 1 ; i < end ; ++i){
            if(A[i] < A[I])
                return i;
        }
        // 向右找到第一个存在 < A[I]的值的分组
        for(int i = groupID + 1 ; i < groupNum ; ++i){
            if(Min[i] < A[I]){
                // 定位组内元素,本组下标范围：[i * groupSize, (i+1) * groupSize)
                int start = i * groupSize;
                int end = min((i+1)*groupSize, (int)A.size());

                for(int j = start ; j < end ; ++j){
                    if(A[j] < A[I])
                        return j;
                }

            }
        }
        // 找不到
        return -1;
    }
    public:
        vector<vector<int>> findNearestLessThan(vector<int> &A){
            int N = A.size();
            // L[i] : i的左侧第一个小于A[i]的数的下标
            // R[i] : i的右侧第一个小于A[i]的数的下标
            vector<int> L(N), R(N);

            Init(A, N);
            for(int i = 0 ; i < N ; ++i){
                L[i] = FindLeftLT(A, i);
                R[i] = FindRightLT(A, i);
            }

            return {L, R};
        }
};

递归线段树

class Solution_Segment_Tree1{
    vector<int> Min;
    void Init(int N){
        Min.resize(N * 4);
    }
    void Build(vector<int> &A, int l, int r, int rt){
        if(l == r){
            Min[rt] = A[l-1];
            return;
        }
        int m = (l + r) / 2;
        Build(A, l, m, 2*rt);
        Build(A, m+1, r, 2*rt+1);
        Min[rt] = min(Min[2*rt], Min[2*rt+1]);
    }
    // 寻找[1, X]区间内最后一个 < V 的下标
    int FindLeftLT(int X, int V, int l, int r, int rt){
        // 如果本节点所有值都 >= V，返回-1
        if(Min[rt] >= V)
            return -1;

        // 如果到叶结点，返回答案。记得减去1
        if(l == r)
            return l - 1;

        int m = (l + r) / 2;
        int ANS = -1;
        //在右侧找答案
        if(X > m)
            ANS = FindLeftLT(X, V, m+1, r, 2*rt+1);
        // 如果右侧找到了答案，返回
        if(ANS != -1)
            return ANS;
        // 在左侧继续找
        ANS = FindLeftLT(X, V, l, m, 2*rt);
        return ANS;
    }
    // 寻找[X, N]区间内第一个 < V 的下标
    int FindRightLT(int X, int V, int l, int r, int rt){
        if(Min[rt] >= V)
            return -1;

        if(l == r)
            return l - 1;

        int m = (l + r) / 2;
        int ANS = -1;
        //在左侧找答案
        if(X <= m)
            ANS = FindRightLT(X, V, l, m, 2*rt);
        // 如果左侧找到了答案，返回
        if(ANS != -1)
            return ANS;
        // 在右侧继续找
        ANS = FindRightLT(X, V, m+1, r, 2*rt+1);
        return ANS;
    }
public:
    vector<vector<int>> findNearestLessThan(vector<int> &A){
            int N = A.size();
            // L[i] : i的左侧第一个小于V[i]的数的下标
            // R[i] : i的右侧第一个小于V[i]的数的下标
            vector<int> L(N), R(N);
            Init(N);
            Build(A, 1, N, 1);
            for(int i = 0 ; i < N ; ++i){
                // 此处i要加上1，因为线段树的下标从1开始
                L[i] = FindLeftLT(i+1, A[i], 1, N, 1);
                R[i] = FindRightLT(i+1, A[i], 1, N, 1);
            }
            return {L, R};
        }
};

非递归线段树

class Solution_Segment_Tree2{
    int STN;
    vector<int> Min;
    void Build(vector<int> &A, int N){
        // 建一颗满二叉树
        STN = 1;
        while(STN < N + 2)
            STN *= 2;
        Min = vector<int>(STN * 2, INT_MAX);

        // 为结点赋值
        for(int i = 0 ; i < N ; ++i)
            Min[STN+i+1] = A[i];
        for(int i = STN - 1 ; i >= 1 ; --i)
            Min[i] = min(Min[i*2], Min[i*2+1]);
    }
    // 寻找[1, X]区间内最后一个 < V 的下标
    int FindLeftLT(int X, int V){
        // 寻找答案所在的树的根结点
        int Root = -1;
        for(int t = STN + X + 1 ; t != 1 ; t >>= 1){
            if((t & 1) && Min[t ^ 1] < V){
                Root = t ^ 1;
                break;
            }
        }

        // 无解，返回-1
        if(-1 == Root)
            return -1;

        // 将Root下移到叶结点
        while(Root < STN){
            if(Min[Root * 2 + 1] < V)
                Root = Root * 2 + 1;
            else
                Root = Root * 2;
        }
        // 返回结点编号
        return Root - STN - 1;
    }
    // 寻找[X, N]区间内第一个 < V 的下标
    int FindRightLT(int X, int V){
        // 寻找答案所在的树的根结点
        int Root = -1;
        for(int s = STN + X - 1 ; s != 1 ; s >>= 1){
            if((~s&1) && Min[s^1] < V){
                Root = s^1;
                break;
            }
        }
        // 无解，返回-1
        if(-1 == Root)
            return -1;

        // 将Root下移到叶结点
        while(Root < STN){
            if(Min[Root * 2] < V)
                Root = Root * 2;
            else
                Root = Root * 2 + 1;
        }
        // 返回结点编号
        return Root - STN - 1;
    }
public:
    vector<vector<int>> findNearestLessThan(vector<int> &A){
            int N = A.size();
            // L[i] : i的左侧第一个小于V[i]的数的下标
            // R[i] : i的右侧第一个小于V[i]的数的下标
            vector<int> L(N), R(N);
            Build(A, N);
            for(int i = 0 ; i < N ; ++i){
                // 此处i要加上1，因为线段树的下标从1开始
                L[i] = FindLeftLT(i+1, A[i]);
                R[i] = FindRightLT(i+1, A[i]);
            }
            return {L, R};
        }
};