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

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]))

Answer 2

您可以将目前为止找到的数字存储在树形图中。将其索引与数字一起存储。当你到达索引i的数字时，在树中查找比array[i]低的最高数字。使用lowerEntry可以让你在Log2N时间内完成，使整体时间为N * Log2N

Answer 3

脚步：

1：对于第一个元素，我们可以在我们的答案中附加-1。

2：循环遍历列表中的第一个元素，并继续将第（i-1）个元素添加到Treeset中。

3：要找到最大的较小元素，我们可以通过set.lower（Element）找到lower_entry

4：如果结果为null，则只需附加-1。

这是一个实现

    StringBuilder b = new StringBuilder();
    TreeSet<Integer> set = new TreeSet<>();
    b.append(-1);
    b.append(" ");
    for(int i = 1; i<a.length; i++){
        set.add(a[i-1]);
        Integer result = set.lower(a[i]);
        if(result != null)
            b.append(result);
        else
            b.append(-1);
        b.append(" ");
    }