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

例如，按以下顺序:

2 6 5 8

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

我知道这可以在 O(n^2) 中轻松完成, 但是有没有更有效的方法呢？

Answer 1

可以使用 stack 在 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 中的最后一个元素将始终是我们要查找的内容。

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