首页 > 代码库 > 给出一个长度为n的数列,请对于每一个数,输出他右边第一个比他大的数。n<=100000.

给出一个长度为n的数列,请对于每一个数,输出他右边第一个比他大的数。n<=100000.

RT,一个ppt里看到的题,不过没讲做法。百度上基本搜不到。自己想了个做法,理论上可行,复杂度也是O(nlogn)。

首先,做一次RMQ,求区间最大值。

对于任意一个数s[i],可以用logn的时间求出他右边第一个比他大的数:

RMQ[i][j] 表示从s[i]开始的2^j个数中的最大值。对于确定的i,RMQ[i][j]随着j的增大肯定是非降的

先判断无解的情况,只要看max(RMQ[i][j],RMQ[n-2^j+1][j]) ,也就是区间[i,n]的最大值是否比s[i]大即可(下面求区间最大值也用该方法,就不写明了),如果是,可能有解,反之无解。

如果有解,也就是在区间[i+1,n]里找到第一个大于s[i]的数;

 

把区间二分,如果左边一半的最大值大于S[i],那么就到左边一半寻找答案,如果左边一半的最大值小于S[i],就到右边一半找,每次查找的范围都缩小了一半。

n个数,每次logn,总的时间复杂度是nlogn。