求该问题时间复杂度最小的算法

1248762042

给出项数为 n 的整数数列 {ai}，下标i从1开始。
定义函数 f(i)
f(i) 代表数列中第 i个元素之后第一个大于ai的元素的下标，即f(i)=min { j }, aj>ai,i<j<=n
若不存在，则 f(i)=0
试求出 f(1)…f(n)
输入格式
第一行一个正整数
n。
第二行
n个正整数 a1…an
输出格式
一行 n个整数 f(1)…f(n)

1248762042

monkey-D 发表于 2021-9-16 15:32
c++有个lower_bound函数（不确定是不是最低复杂度）

可是这个lower_bound要求数组排序啊

1248762042

jhq999 发表于 2021-9-16 17:20
{1,2,0,8,2}
f(1)=2;f(2)=4;f(3)=4;f(4)=0;f(5)=0
我理解的对吗？

理解的是对的  但就是想找一种时间复杂度 小于 O(n2)的算法