找到数组的忍者索引

Question

这是我遇到的一个有趣的难题,根据该难题,给定一个数组,我们需要在其中找到忍者索引.

忍者指数由以下规则定义:

索引K使得具有较小索引的所有元素具有低于或等于A [K]的值,并且具有较大索引的所有元素具有大于或等于A [K]的值.

例如,考虑:

A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.

在这种情况下,5是忍者指数,因为对于r = [0,k]和A [5] <= A [r] r = [k,n],A [r] <= A [5].

我们应该遵循什么算法才能在O(n)中找到它.我已经有一个强力O(n ^ 2)解决方案.

编辑:可能有超过1个忍者指数,但我们需要优先找到第一个.如果没有NI,那么我们将返回-1.

Answer 1

预计算阵列所有后缀的最小值和所有前缀的最大值.使用此数据,可以在O(1)中检查Ninja中的每个元素.