创建以线性时间

Question

一个图案化阵列给定一个整数数组P [1..N]，我们要建立一个数组S [1..N]：在P [1

其中成员。 .i-1]大于P [i]，我们选择具有最大指数的P [k]（1 < = k < i < = n）。 S [i]将保持P [k]的值。如果在P [1..i-1]中没有大于P [i]的数字，我们在S [i]中放置0。

显然，S []中的第一个元素将为0，因为之前没有元素。其他可以通过数组P []迭代找到，但是，这将需要O(n^2)，因为它是系列1+2+...+n=[1/2n(n+1)]的总和。

有没有办法在线性时间做到这一点？我曾考虑过使用堆栈，因为它有助于以更大的值提取最高索引，但是，我尝试实现它的任何方式仍然需要我通过创建的堆栈，所以实际上更糟 - 时间到创建堆栈，并弹出时间，直到达到所需的元素，一遍又一遍。也许还有另一种方式？

任何想法/建议/提示如何做到这一点？

实例：

P[5,4,9,7,8]-->S[0,5,0,9,9] 
P[1,5,2,3]-->S[0,0,5,5] 

澄清：

我们应该分配给S [I]的最高索引数目，仍然大于P [i]于P [1。 .I-1]。例如，假设P [8,2,1]。虽然8是最大的值，S [3]将保持值2，因为它是最高的索引号，仍然大于P [3]。 - > S [0,8,2]。

编辑：

我相信我有一个O（n）的溶液中，使用堆栈。在伪代码中的想法：

BuildS(P[]) 
    Temp-StackNIL 
    for(i<--1 up to n) 
     while(Temp-Stack≠NIL) 
      if(P[i]<=top[Temp-Stack]) 
       pop(Temp-Stack) //goes back to while 
      else 
       S[i]<--top[Temp-Stack] 
       push(Temp-Stack,P[i]) //goes back to for 
     S[i]<--0 //out of while 
     push(Temp-Stack,P[i]) //goes back to for 

我说得对吗？

Answer 1

我不认为有O（n）解决方案，但我想出了O（n log n）。

假设我们有binary search tree（BST）。主回路伪代码：

for i in [0, len(P)): 
    S[i] = BST.search(P[i])  
    BST.insert(P[i], i) 

我认为search回报S[i]为P[i]。

def search(value): 

    def getSbyIndex(index): 
     return index == -inf ? 0 : P[index] 

    curVertex = BST.root 
    maxIndex = -inf 
    while: 
     if curVertex.value > value: 
      if !(curVertex.leftChild exists): 
       return getSbyIndex(maxIndex) 
      else: 
       maxIndex = max(maxIndex, curVertex.index, curVertex.rightChild.subtreeMaxIndex) 
       if curVertex.leftChild.value <= value: 
        return getSbyIndex(maxIndex) 
       else: 
        curVertex = curVertex.leftChild 
     else: 
      if !(curVertex.rightChild exists): 
       return getSbyIndex(maxIndex) 
      else: 
       curVertex = curVertex.rightChild 

我写search未优化（，也没有检查一些不存在的情况下，顶点为简单起见，要小心！）故意给你的总体思路。我们从BST的根部开始，根据需要更新maxIndex（见下面的解释）。我们的BST的每个叶（其实际上表示一些P [X]）含有5个字段：

• leftChild
• rightChild
• 值（即P [X]）
• 索引（X）
• subtreeMaxIndex（以当前顶点为根的子树的顶点之间的最大.index）

那么它什么时候需要？假设我们有curVertex.value <= value。这意味着我们必须去正确的子树。左子树的任何vertex.value也是<= value，所以左子树和当前顶点中没有顶点（P[y]）满足P[y] > P[new]条件，因此我们不更改maxIndex。

同样，假设我们有curVertex.value > value，这导致我们到左子树。但是这次右子树的任何vertex.value是vertex.value > value，所以在当前和右子树顶点之间的所有P[y]实际上大于P[new]，所以我们必须找到它们的最大索引，其等于max（curVertex.index，curVertex.rightChild .subtreeMaxIndex），并尝试使用它更新maxIndex。

我们最需要的是insert。

def insert(value, index): 
    newVertex = BST.insertNode(value) 
    newVertex.index = index 
    curVertex = newVertex 
    while curVertex is not BST.root: 
     curVertex.subtreeMaxIndex = max(curVertex.index, curVertex.leftChild.subtreeMaxIndex, curVertex.rightChild.subtreeMaxIndex) 
     curVertex = curVertex.parent 

在这里，我没有再次检查孩子的存在，并且还添加了parent字段。 BST.insertNode只是一个基本的BST插入方法，它返回一个新的顶点对象。之后，我们只需向上到根，为路径上的每个顶点更新.subtreeMaxIndex。

总体而言，我们对主回路的n迭代和log n两个insert和search调用，所以最终的复杂度为O（n log n）的。

Answer 2

实际上有在O(n)

的解决方案的想法是跟踪，同时通过P循环和比较P[i]这个值遇到的最高值。

这里是我想出了（使用你的第一个例子）

P = [1,5,2,3] 
S = [] 
highest = 0 

for i in P 
    if highest < P[i] 
     highest = P[i] 
     S[i] = 0 
    else 
     S[i] = highest 

我这里假设你只使用值的伪码> = 0，但如果你有负值highest应与最小值进行初始化可能。