这个问题在这里已有答案：
- 最大元素出现在数组中每个元素的右侧 3个答案
3192
2017-07-12 05:57
起源
你需要找到每个索引吗？或者只是给定的指数？ - cricket_007
所以输入是 A 和 i，期望的输出是 j，s.t。陈述条件成立？ - Nicolas
我需要它用于所有索引..不仅仅是一个。输入是 A 输出是一个数组 B 含 j 对于所有指数 i - Sam Radhakrishnan
你的蛮力企图是什么样的？ - cricket_007
从索引i + 1开始并遍历到结束并跟踪大于的最小元素 A[i]。 - Sam Radhakrishnan
答案:
O（nlogn）下界证明:(对于基于比较的算法）
假设我们有一个基于比较的算法，可以在O（n）中完成这个任务。对于每个索引，我们在其右边有更大的元素（比如R [i]）。
类似地，我们可以在反向输入数组上运行此算法，然后反转结果。对于每个索引，我们在其左边有更大的元素（比如L [i]）。
这意味着在O（n）中我们对每个元素都有，数组中的直接更大元素= min（R [i]，L [i]）。
我们现在可以使用此信息对数组进行排序。
找到数组中的最小元素。找到它的继承者（直接更大的元素），然后是它的继承者的继承者等等。因此，您将按排序顺序获得整个数组。
仅使用比较（矛盾）在O（n）中对数组进行排序。
O（nlogn）算法：
从阵列右侧开始构建平衡BST。节点将包含值和相应的索引。
然后，对于遇到的每个新元素，将其插入BST将获得相应的最接近的较大索引/值。
9
2017-07-12 06:19
我们无法完全根据您描述的方式进行排序。我们右边有更大的元素，而不是整体。你能澄清一下吗？ - Akashdeep Saluja
@AkashdeepSaluja我们发现它的右边有一个更大的元素（比如R [i]）。类似地，我们可以通过反向运行该算法找到其左边的直接较大元素（比如L [i]）。这意味着立即有更大的元素= min（R [i]，L [i]）。 - Abhishek Bansal
人们也可以获得 O(n log n)算法通过创建一个包含原始数组中的值和索引的类型，并对这些值进行排序。 - Codor
@Codor，我们希望立即将更多元素“推向正确”。在排序之后，我们如何在总O（n）时间内确定每个元素在其右边的直接更大元素？ - Abhishek Bansal
您的下限持有证明 只要 如果我们的算法是基于比较的。我们可能会想出计算排序并获得O（n + k）解决方案的地方 k 取决于数组中的最大值。 - Bakuriu