查找序列中每个元素的前导

Question

给定一个序列a[1], a[2], a[3] .... a[n],我必须为每个a[i]元素找到一个元素a[j],其中a[j]序列中的第一个元素就是a[i - 1], a[i - 2], a[i - 3]....这样a[j] < a[i].

换句话说,我必须找到a[j]哪里a[j] < a[i]和1<=j<i.但如果有多个这样的元素,我必须选择最接近的元素a[i].

例如,按以下顺序:

2 6 5 8

我必须为6和5输出2,为8输出5.

我知道这可以很容易地完成O(n^2),但有没有更有效的方法呢？

Answer 1

O(n)可以使用堆栈来完成。

a = your array
d = a stack
d.push(a[1])
for i = 2 to n do
  while d.top > a[i] do
    d.pop()

  print d.top if it exists, else -1
  d.push(a[i])

基本上，我们保持d排序并确保其最后一个元素始终小于a[i]。这样，最后一个元素d将始终是我们要寻找的元素。

由于嵌套循环，线性复杂性可能不会立即明显，但观察每个元素最多会离开和进入堆栈一次，因此次数是恒定的。