数组中前一个最近的更大元素

Question

我试图解决以下问题。给定一个实数数组 [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1]，对于每个元素，我需要在数组中找到最近的前一个大于它的元素。

例如，第一个元素（7）没有比它更大的元素，因此它为NaN。对于第二个元素（2），7是更大的元素。因此，最终答案如下： [NaN, 7, 7, NaN, 8, 8, 8, 8, 7, 4, 3, 1]。当然，我可以检查每个元素的所有前面的元素，但这在数组元素数量方面是二次的。

我的另一种方法是维护先前元素的排序列表，然后选择第一个大于当前元素的元素。这对我来说听起来像是对数线性（我不确定）。有没有更好的方法来解决这个问题？

- randomizer

---

排序的时间复杂度是 O(nlogn) 而不是 O(logn)。我认为 O(nlogn) 是最好的方法。 - levi

@levi 我认为对数线性的时间复杂度是O(nlogn)。 - randomizer

对于每个数字，你只需要找到一个更大的先前数字吗？还是必须是最近的更大数字？在第一种情况下，可以轻松地在O(n)时间内完成。 - HugoRune

如果我的理解是正确的，您想比较当前元素和上一个元素，并从这两个元素中找到最大值是吗？ - maxspan

抱歉@HugoRune，我需要找到最近的更大元素。我会更新答案。 - randomizer

你正在寻找某种斐波那契数列。 - maxspan

Answer 1

以下是一种实现方式

create a stack which is initially empty
for each number N in the array
{
    while the stack is not empty
    {
        if the top item on the stack T is greater than N
        {
            output T (leaving it on the stack)
            break
        }
        else
        {
            pop T off of the stack
        }
    }
    if the stack is empty
    {
        output NAN
    }
    push N onto the stack
}

以样本数组 [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1] 为例，以下是算法的解决过程。

stack           N             output  
-               7               NAN 
7               2               7
7 2             4               7
7 4             8               NAN
8               1               8
8 1             1               8
8 1             6               8
8 6             7               8
8 7             4               7
8 7 4           3               4
8 7 4 3         1               3

理论上，堆栈不需要保留小数字，因为它们永远不会成为输出的一部分。例如，在序列7、2、4中，不需要2，因为任何小于2的数字也一定小于4。因此，堆栈只需要保留7和4。

复杂度分析

算法的时间复杂度可以表示为O(n)：

1. 恰好有n个推入（输入数组中的每个数字仅被推入堆栈一次）； 2. 最多有n个弹出（一旦数字从堆栈中弹出，就会被丢弃）； 3. 最多有n个失败比较（因为数字在失败比较后被弹出并丢弃）； 4. 最多有n个成功比较（因为算法在成功比较后移动到输入数组中的下一个数字）； 5. 恰好有n个输出操作（因为算法为输入数组中的每个数字生成一个输出）。

因此，我们得出结论：算法执行的最多操作次数为5n，时间复杂度为O(n)。

- user3386109

---

哇，看起来很不错。谢谢你。不过还需要了解它的工作原理。 - randomizer

你可以认为你的算法是线性的，因为你最多只有 n 次弹出操作，并且在每一步中你都会进行 1 + (该步骤中弹出次数) 次比较。 - JuniorCompressor

@JuniorCompressor 是的，完全正确。我在答案中添加了一个部分来解释时间复杂度。 - user3386109

Answer 2

我们可以为每个数组元素保留其最近大于它的元素的索引。当我们处理新元素x时，我们检查前一个元素y。如果y比x大，则我们找到了我们想要的。如果不是，则我们检查y的最近大于它的元素的索引是哪个。我们继续这个过程直到找到我们需要的元素及其索引。使用Python实现：

a = [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1]
idx, result = [], []
for i, v in enumerate(a, -1):
    while i >= 0 and v >= a[i]:
        i = idx[i]
    idx.append(i)
    result.append(a[i] if i >= 0 else None)

结果：

[None, 7, 7, None, 8, 8, 8, 8, 7, 4, 3]

这个算法是线性的。当索引j未被检查时，因为我们正在寻找索引i>j的最近更大元素，所以从现在开始，i将指向比j更小的索引，而j将不再被检查。

- JuniorCompressor

---

抱歉，我无法为您的答案点赞。当我有足够的声望时会这样做。非常感谢您的帮助。 - randomizer

Answer 3

为什么不定义一个名为“current_largest”的变量并从左到右迭代数组呢？在每个元素中，当前最大值是先前的最大值，如果当前元素更大，则将当前最大值分配给当前元素。然后移动到下一个元素。

编辑： 我刚刚重新阅读了你的问题，可能误解了它。您要找到所有较大的先前元素吗？

编辑2： 对我来说，当前最大值方法似乎可行。您只需要在分配新值之前记录current_largest即可。例如，在Python中：

current_largest = 0
for current_element in elements:
    print("Largest previous is "+current_largest)
    if(current_element>current_largest):
        current_largest = current_element

如果你想要一个这样的数组，那么只需将值推送到数组中，而不是打印语句。

- user2027202827

---

我不能得到当前最大值，因为我不需要找到最大的元素。我需要找到每个元素的前一个最大值。例如，如果在数组[100, 2, 3, 10, 4, 9]中，如果我保存最大值，那么对于元素9，我将得到100，但应该得到10。 - randomizer

Answer 4

根据我对你问题的最好理解，以下是一个解决方案。 工作示例：JSFIDDLE

 var item = document.getElementById("myButton");
item.addEventListener("click", myFunction);
function myFunction() {
    var myItems = [7, 2, 4, 8, 1, 1, 6, 7, 4, 3, 1];
    var previousItem;
    var currentItem;
    var currentLargest;
    for (var i = 0; i < myItems.length; i++) {
        currentItem = myItems[i];
        if (i == 0) {
            previousItem = myItems[0];
            currentItem = myItems[0];
            myItems[i] = NaN;
        }
        else {
            if (currentItem < previousItem) {
                myItems[i] = previousItem;
                currentLargest = previousItem;
            }
            if (currentItem > currentLargest) {
                currentLargest = currentItem;
                myItems[i] = NaN;
            }
            else {
                myItems[i] = currentLargest;
            }
            previousItem = currentItem;
        }
    }
    var stringItems = myItems.join(",");
    document.getElementById("arrayAnswer").innerHTML = stringItems;
}

- maxspan

---

这看起来不像是正确的答案。我应该得到像这样的东西：[NaN，7，7，NaN，8，8，8，8，7，4，3，1]，但我看到的是[7，7，NaN，NaN，8，1，NaN，NaN，7，4，3]。 - randomizer