3

这是一个算法优化问题。

我有一个整数数组A，想要构建一个数组B，其中包含元素的B[i]索引，使得 ( )jA[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)或证明它是不可能的？

4

1 回答 1

4

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

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

下面的 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一次，因为每个元素只能执行一次。或者，换句话说，每个元素最多被推送和弹出一次。

于 2013-04-15T17:57:31.713 回答