网站建设报价单表格,阳江招聘,dplayer wordpress,做网站好赚钱吗题目
有一个长度为 n 的序列 A#xff0c;A[i] 表示序列中第 i 个数(1in)。她定义序列中第 i 个数的 prev[i] 值 为前 i-1 个数中比 A[i] 小的最大的值#xff0c;即满足 1ji 且 A[j]A[i] 中最大的 A[j]#xff0c;若不存在这样的数#xff0c;则 pre…题目
有一个长度为 n 的序列 AA[i] 表示序列中第 i 个数(1in)。她定义序列中第 i 个数的 prev[i] 值 为前 i-1 个数中比 A[i] 小的最大的值即满足 1ji 且 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的apilower_bound(); lower_bound() 函数用于在有序区间内查找大于等于目标值的第一个元素。也就是说使用该函数在指定范围内查找某个目标值时最终查找到的不一定是和目标值相等的元素还可能是比目标值大的元素。 但是返回的迭代器的前一个迭代器则是小于等于目标值的最后一个元素这一点和前i-1个数中比A[i]小的最大值就不谋而合了。 代码如下
setlongmySet;
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);
}
