arrays - 最大限度。大于数组中给定数字的数字的距离

Question

我正在经历一个面试问题..并想出了需要找到的逻辑:

Find an index j for an element a[j] larger than a[i] (with j < i), such that (i-j) is the largest. And I want to find this j for every index i in the array, in O(n) or O(n log n) time with O(n) extra space.`

到目前为止我做了什么:

1) O(n^2)通过使用简单的 for loop

2) 建立平衡的 B.S.T.当我们从左到右扫描元素时 i 'th 元素找到比它大的元素的索引。但我意识到它很容易成为 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 (i-j)==(2-0)
for 6 , ans=-1
for 0 , ans=4 (i-j)==(4-0)

Answer 1

创建一个最大值的辅助数组，让它成为 maxs，它基本上包含数组中的最大值，直到当前索引。

形式上:maxs[i] = max { arr[0], arr[1], ..., arr[i] }

请注意，这是可以在 O(n)

中完成的预处理步骤

现在对于每个元素 i，您正在寻找 maxs 中第一个大于 arr[i] 的元素。这可以使用二进制搜索来完成，并且是 O(logn) 每个操作。

给你总共 O(nlogn) 的时间和 O(n) 的额外空间。