涉及分区和选择的算法

Question

我理解这道题用selection和partition可以最高效的解决，两者都可以在线性时间内完成。我的想法是选择数组 O(n) 中第 n 个最小的元素，在给出的示例中为 34，因此在本例中为 j = 3。然后from i = 1 to j - 1，如果序列递减，设置B[i] = j，序列增加的时刻，设置B[ i] = i + 1 然后停止。递归调用数组 A[j ... n] 上的过程。我认为这根本没有效率，也不确定它是否正确或我的算法的最终复杂度是多少。

总结

(1) 使用确定性选择算法 o(n) 选择第 n 个最小的(索引 j)

(2)

function:
    for i = 1 to n do
      for j = i + 1 to n do
         if A[j] > A[i] then B[i] = j , B[j] = n + 1
         for k = i + 1 to j - 1 do
            if A[k] < A[k + 1]
               B[k] = j
            else
               B[k] = k + 1
               recursive function(A[j + 1, ... n]) // recursively perform procedure on portion of array starting from j + 1 (after max) to n.

Answer 1

这个问题有一个基于堆栈的标准解决方案，其复杂度为 O(n)。 http://www.geeksforgeeks.org/next-greater-element/ 有很好的解释.

这是该算法的 Python 实现示例:

def next_greater_element(A):
    """Return an array of 1-based indices to the next strictly greater element, n+1 if none exists"""
    i=0
    n = len(A)
    NGE=[n+1]*len(A)
    stack=[]
    while i<len(A)-1:
        stack.append(i)
        while stack and A[stack[-1]]<A[i+1]:
            x=stack.pop()
            NGE[x]=i+2
        i+=1
    return NGE

A = [8,3,34,13,1,2,21,5]
B = next_greater_element(A)
print B

这打印

[3, 3, 9, 7, 6, 7, 9, 9]

要点是每个元素入栈一次，出栈一次，所以内层的while循环最多可以执行n次。