通过数组中的索引号找到最接近的索引号

Question

这是算法优化问题。

我有一个整数数组A和要构建阵列B使得B[i]包含的元素的索引j在A[j]使得（B[i] = j）

1. j > i 
2. A[j] < A[i] 
3. j is minimum of all possible j's. 

例如，如果A是：

A = [1,5,6,4,3,1,2] 

然后B将会（从0开始索引）

B = [-1,3,3,4,5,-1,-1] 

B[0] = -1因为没有小于1的数字，其索引大于0。 B[1] = 3，因为A[3]是中包含的数字小于A[1]=5的索引1的右边最接近的元素。等等。

我知道解决方案O(n*log(n))复杂性使用二叉搜索树。我怎样才能将复杂性提高到O(n)或者证明这是不可能的？

Answer 1

除非我误解了这个问题，你可以通过一个简单的从左到右的扫描来解决它，保留一堆你尚未遇到过小元素的索引。 （由于显而易见的原因，对应于堆栈上的索引的值必须是单调不减少的。）

对于输入列表中的每个值，尽管该值小于对应于顶部索引的值（如果有的话） ），将输出列表的相应元素设置为当前输入值的索引并弹出堆栈。

以下小Python程序说明：

def ind(a): 
    b = [-1] * len(a) 
    stack = [] 
    for i in range(len(a)): 
    v = a[i] 
    while stack and a[stack[-1]] > v: 
     j = stack.pop() 
     b[j] = i 
    stack.append(i) 
    return b 

证明它是O(n)：for循环显然是执行n倍。 while循环的主体最多执行n次，因为每个元素只能发生一次。或者，换句话说，每个元素最多只能被推送一次。