java - 如何在小于元素的元素左侧找到最大元素？

Question

假设我有一个这样的整数数组:

{ 3, 1, 6, 8, 2, 0, 1 }

我需要在每个元素的左侧找到小于该元素的最大元素，或者如果该最大元素不存在则打印 -1。所以，这个问题的解决方案是:

{ -1, -1, 3, 6, 1, -1, 0}

我可以使用两个循环在 O(n^2) 中解决这个问题。内循环将找到小于给定元素的最大元素。但是有没有更好的方法来解决这个问题？

Answer 1

虽然这个问题不是关于 finding the rightmost element on the left hand side that is smaller 的，一个涉及堆栈的可爱线性时间算法的问题，它是密切相关的。要解决此问题，请按值对数组索引和值对进行排序，然后从链接的问题运行算法，将索引视为值。这避免了二叉搜索树强加的常数因子。

由于对不同元素进行排序是线性时间可简化为该问题，因此 O(sort(n)) 的运行时间或多或少是最优的。

Python 实现(比预期更微妙；请注意，sorted 不得重新排列比较相等的元素)。

def alg(lst):
    indexes = sorted(range(len(lst) - 1, -1, -1), key=lst.__getitem__)
    stack = []
    out = [-1] * len(lst)
    for i in indexes:
        while stack and i < stack[-1]:
            del stack[-1]
        if stack:
            out[i] = lst[stack[-1]]
        stack.append(i)
    return out


print(alg([3, 1, 6, 8, 2, 0, 1]))