Sam*_*nan 11 arrays algorithm asymptotic-complexity
给定一个数组,对于每个元素,我需要找到给定元素右边的最大元素,该元素大于当前元素.
数学上,对于i数组中的每个索引A,我需要找到j这样的索引
A[j] > A[i]
j > i
A[j] - A[i] is minimum
我需要找到j每个索引i
蛮力解决方案将是O(n^2),我希望做得更好.我认为O(n log n)使用自平衡BST可以实现解决方案,但这似乎相当复杂.而且我需要一个O(n)解决方案.
有O(n)这个问题的解决方案吗？是否有证据表明下限是 O(n log n)？
O(nlogn)下界证明:(对于基于比较的算法)
假设我们有一个基于比较的算法,可以在O(n)中完成这个任务.这是针对每个指数,我们在其右边有更大的元素(比如R [i]).
类似地,我们可以在反向输入数组上运行此算法,然后反转结果.对于每个索引,我们在其左边有更大的元素(比如L [i]).
这意味着在O(n)中我们对每个元素都有,数组中的直接更大元素= min(R [i],L [i]).
我们现在可以使用此信息对数组进行排序.
找到数组中的最小元素.找到它的继承者(直接更大的元素),然后是它的继任者的继承者等等.因此,您将按排序顺序获得整个数组.
仅使用比较(矛盾)在O(n)中对数组进行排序.
O(nlogn)算法:
从阵列右侧开始构建平衡BST.节点将包含值和相应的索引.
然后,对于遇到的每个新元素,将其插入BST将获得相应的最接近的较大索引/值.