algorithm - 在数组中查找小于给定索引处数字的最近索引号

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]是最接近索引 1 的元素在A包含小于 A[1]=5 的数字.等等。

我知道 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 次，因为每个元素只能执行一次。或者，换句话说，每个元素最多被压入和弹出一次。