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

Question

给定一个未排序的数组，找到索引之间的 max j - i 差异使得 j > i 和 a[j ] > a[i] 在 O(n) 中。我能够在 O(n^2) 复杂性中使用简单的方法找到 j 和 i 但想知道如何在O(n)？

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

Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}

Output: 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 弹出一个元素.在每个这样的步骤中，如果 a[S[head]] < a[T[head]]，我们会在 S 和 T 的头部记录差异。 .最大的差异会给您答案。

编辑:这是一个用 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