我正在经历一个面试问题..并提出了需要找到的逻辑:
查找大于(with )
j的元素的索引,这是最大的.而且我想为数组中的每个索引找到它,或者在额外的空间中找到它a[j]a[i]j < i(i-j)jiO(n)O(n log n)O(n)
我到目前为止做了什么:
1)O(n^2)通过使用简单的for loops
2)当我们从左到右扫描元素时,构建平衡的BST,并且i元素的元素查找索引大于它.但我意识到它可以很容易地O(n)用于单个元素,因此O(n^2)对于整个阵列.
我想知道是否可以在O(n)或中进行O(n log n).如果是,请提供一些提示.
编辑:我想我无法解释我的问题.让我清楚地解释一下:我希望arr[j]左边的arr[i]这(i-j)是最大可能的,arr[j]>arr[i]并且找到所有索引i即for(i=0 to n-1).
编辑2:示例 - {2,3,1,6,0}
for 2 , ans=-1
for 3 , ans=-1
for 1 , ans=2 (ij)==(2-0)
for 6 , ans=-1
for 0 , ans=4 (ij)==(4-0)
ami*_*mit 12
创建一个最大值的辅助数组,让它成为maxs,它基本上包含阵列上的最大值,直到当前索引.
形式上: maxs[i] = max { arr[0], arr[1], ..., arr[i] }
请注意,这是可以在其中完成的预处理步骤 O(n)
现在,对于每个元素i,您正在寻找maxs中第一个大于的元素arr[i].这可以使用二进制搜索来完成,并且是O(logn)按操作.
为您提供总O(nlogn)时间和O(n)额外空间.