这是我遇到的一个有趣的谜题，根据这个谜题，给定一个数组，我们需要在其中找到忍者索引。
Ninja 索引由以下规则定义：
一个索引 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是 ninja index ，因为 A[r]<=A[5] for r = [0,k] 和 A[5]<=A[r] r = [k,n]。
我们应该遵循什么算法在 O(n) 中找到它。我已经有一个蛮力 O(n^2) 解决方案。
编辑：可以有超过 1 个 ninja index ，但我们最好找到第一个。如果没有 NI ，那么我们将返回 -1。
预先计算数组所有后缀的最小值和所有前缀的最大值。有了这个数据，每个元素都可以在 O(1) 中检查 Ninja。
一个需要 O(3n) 操作的 python 解决方案
def n_index1(a):
max_i = []
maxx = a[0]
for j in range(len(a)):
i=a[j]
if maxx<=i and j!=0:
maxx=i
max_i.append(1)
else:
max_i.append(-1)
return max_i
def n_index2(a):
max_i = []
maxx = -a[len(a)-1]
for j in range(len(a)-1,-1,-1):
i=-a[j] # mind the minus
if maxx<=i and j!=len(a)-1:
maxx=i
max_i.append(1)
else:
max_i.append(-1)
return max_i
def parse_both(a,b):
for i in range(len(a)):
if a[i]==1 and b[len(b)-1-i]==1:
return i
return -1
def ninja_index(v):
a = n_index1(v)
b = n_index2(v)
return parse_both(a,b)
另一个 Python 解决方案，遵循相同的通用方法。可能会短一些。
def ninja(lst):
maxs = lst[::]
mins = lst[::]
for i in range(1, len(lst)):
maxs[ i] = max(maxs[ i], maxs[ i-1])
mins[-1-i] = min(mins[-1-i], mins[-i ])
return [i for i in range(len(lst)) if maxs[i] <= lst[i] <= mins[i]]
我想它可以对列表复制操作进行一些优化，但这样更简洁。
这个直截了当的 Java 代码计算最左边的索引，该索引具有“所有向右的元素都不少”的属性：
private static int fwd(int[] a) {
int i = -1;
for (int j = 0; j < a.length - 1; j++) {
if (a[j + 1] >= a[j] && i == -1) {
i = j + 1;
} else if (i != -1 && a[j + 1] < a[i]) {
i = -1;
}
}
return i;
}
几乎相同的代码计算具有属性“向左的所有元素都不大于”的最左边的索引：
private static int bwd(int[] a) {
int i = -1;
for (int j = 0; j < a.length - 1; j++) {
if (a[j + 1] >= a[j] && i == -1) {
i = j + 1;
} else if (i != -1 && a[j + 1] < a[i]) {
i = -1;
}
}
return i;
}
如果结果相同，则找到最左边的 Ninja 索引。