在一个数组中找到下一个更大的元素

Question

给定一个数组, 对于每个元素，我需要找到在该元素右边且比当前元素大的最小元素。

数学上来说， 对于数组 A 中的每个下标 i，我需要找到下标 j，使得

A[j] > A[i]
j > i
A[j] - A[i] is minimum

我需要找到每个索引(i)对应的j值。

暴力解法时间复杂度为O(n^2)，希望能够得到更好的方法。我考虑使用平衡二叉树达到O(n log n)的时间复杂度，但这看起来很复杂。此外，我需要一个O(n)的解决方案。

有没有O(n)的解决方案？有没有证明下限是O(n log n)的证据？

- Sam Radhakrishnan

---

你需要找到每个索引吗？还是只需要给定的索引？ - OneCricketeer

所以输入是 A 和 i，期望的输出是 j，满足所述条件？ - Nicolas

我需要适用于所有索引而不仅仅是一个。输入为“A”，输出是包含所有索引“i”的“j”的数组“B”。 - Sam Radhakrishnan

你的暴力破解尝试是什么样子的？ - OneCricketeer

从索引 i+1 开始遍历到末尾并记录大于“A[i]”的最小元素。 - Sam Radhakrishnan

Answer 1

O(nlogn)下界的证明（适用于基于比较的算法）： 假设我们有一个能以O(n)完成此任务的基于比较的算法。即对于每个索引，我们都有其右侧的立即大元素（记为R[i]）。

同样地，我们可以在反转的输入数组上运行此算法，然后再将结果反转。对于每个索引，我们都有其左侧的立即大元素（记为L[i]）。

这意味着在O(n)时间内，对于每个元素，在数组中都有立即大的元素=min(R[i], L[i])。

我们现在可以使用这些信息对数组进行排序。

找到数组中的最小元素。找到它的后继（立即大的元素），然后是后继的后继等。这样你就得到了整个排好序的数组。

只使用比较就在O(n)时间内排序数组（矛盾）。 O(nlogn)算法： 从数组的右侧开始构建平衡二叉树。节点包含值和相应的索引。

然后遇到每个新元素时，将其插入到BST中会获得相应的最近更大的索引/值。

- Abhishek Bansal

---

我们无法完全按照您描述的方式进行排序。我们只有右侧较大的元素，而不是整体上的。您能否请澄清一下？ - Akashdeep Saluja

@AkashdeepSaluja 我们找到右侧的立即较大元素（称为R[i]）。同样，我们可以通过在反向运行此算法来找到左侧的立即较大元素（称为L[i]）。这意味着具有立即较大元素= min(R[i], L[i])。 - Abhishek Bansal

通过创建一个包含原始数组中的值和索引的类型，并对这些值进行排序，也可以获得O(n log n)算法。 - Codor

你的下界证明仅当我们的算法是基于比较的才成立。我们可能会想出一些像计数排序之类的东西，并获得一个O(n+k)的解决方案，其中k取决于数组中的最大值。 - Bakuriu

@AbhishekBansal 不，不是这样的。我并不是说找到这样的算法很容易，但我相信这样的算法可能存在。如果你认为不是这种情况，你应该在你的答案中添加一个证明，证明不包含数组元素之间比较的算法是不正确的...祝你好运提供这样的证明。 - Bakuriu