題目

有一個長度為 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);
}