得到前i-1个数中比A[i]小的最大值，使用set，然后二分查找

题目

有一个长度为 n 的序列 A，A[i] 表示序列中第 i 个数(1<=i<=n)。她定义序列中第 i 个数的 prev[i] 值 为前 i-1 个数中比 A[i] 小的最大的值，即满足 1<=j<i 且 A[j]<A[i] 中最大的 A[j]，若不存在这样的数，则 prev[i] 的值为 0。

思路

很显然，使用双for循环的复杂度为O(n^2);
伪代码如下：

for (int i = 1; i < a.size(); i++) {
    int max = 0;
    for (int j = 1; j < i; j++) {
        if(a[j] < a[i] && a[j] > max){
            max = a[j];
        }
    }
    prev[i] = max;
}

此时可以借助二叉搜索树来完成这个任务，这样复杂度就是O(nlogn)了，由于容器set的底层是红黑树，我们可以直接使用。
这里介绍一下set的api：lower_bound();
lower_bound() 函数用于在有序区间内查找大于等于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。
但是返回的迭代器的前一个迭代器则是小于等于目标值的最后一个元素，这一点和前i-1个数中比A[i]小的最大值就不谋而合了。
代码如下：

set<long>mySet;
for(int i = 0; i < n; i++)
{
	int tmp;
	//获取A[i]
	cin >> tmp;
	//基于set数据结构进行二分查找
	auto iter = mySet.lower_bound(tmp);
	//前i-1个数中比A[i]小的最大值为(*--iter)
	if (iter != mySet.begin())	prev[i] = (*--iter);
	mySet.insert(tmp);
}