找到j和i索引之间的最大差异,使得在U(n)中j> i和a [j]> a [i]

Question

给定一个排序的数组,找到max j - i这样指数之间的差异j > i,并a[j] > a[i]在O(n).我能够在复杂性中找到j并i使用琐碎的方法,O(n^2)但想知道如何做到这一点O(n)？

输入:{9,2,3,4,5,6,7,8,18,0}

输出:8(j = 8,i = 0)

输入:{1,2,3,4,5,6}

输出:5(j = 5,i = 0)

Answer 1

为了简洁起见,我将假设所有元素都是独一无二的.该算法可以扩展为处理非唯一元素的情况.

首先,注意观察,如果x和y分别是你想要的最大值和最小值的位置,那么就不可能有任何a[i] > a[x]和i > x,同样,不a[j] < a[y]和j < y.

因此,我们沿着数组扫描a并构建一个数组S,以S[i]保存最小元素的索引a[0:i].类似地,一个数组T保存最大元素的索引a[n-1:i](即向后).

现在我们可以看到,a[S[i]]和a[T[i]]必然减少序列,因为他们是直到最小i和最大距离n,直至i分别.

所以现在我们尝试进行类似合并的排序程序.在每一步,如果a[S[head]] < a[T[head]],我们弹出一个元素T,否则我们弹出一个元素S.在每个这样的步骤中,我们记录S和T的头部的差异a[S[head]] < a[T[head]].这种差异的最大值可以为您提供答案.

编辑:这是Python实现算法的简单代码.

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist