algorithm - 查找序列中每个元素的前驱

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]wherea[j] < a[i]和1<=j<i。但是如果有多个这样的元素，我必须选择最接近的一个a[i]。

例如，按以下顺序：

2 6 5 8

我必须为 6 和 5 输出 2，为 8 输出 5。

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

score 3 · Accepted Answer

可以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将永远是我们正在寻找的。

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

1 回答 1