5

i was going through an interview question ..and came up with logic that requires to find:

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.`

What I have done until now :

1) O(n^2) by using simple for loops

2) Build balanced B.S.T. as we scan the elements from left to right and for i'th element find index of element greater than it. But I realized that it can easily be O(n) for single element, therefore O(n^2) for entire array.

I want to know if it is possible to do it in O(n) or O(n log n). If yes, please give some hints.

EDIT : i think i am unable to explain my question . let me explain it clearly: i want arr[j] on left of arr[i] such that (i-j) is the largest possible ,and arr[j]>arr[i] and find this for all index i i.e.for(i=0 to n-1).

EDIT 2 :example - {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)

4

4 回答 4

13

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

正式地：maxs[i] = max { arr[0], arr[1], ..., arr[i] }

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

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

为您提供总O(nlogn)时间和O(n)额外空间。

于 2013-10-14T08:31:17.113 回答
2

您可以在 O(n) 时间内使用堆栈数据结构为您尚未找到解决方案的数组索引执行此操作。它可以实现为最多包含 n 个元素的数组。

从左到右迭代输入数组，从最后一个元素开始：

  • 从堆栈中弹出数组元素小于当前元素的所有索引。将当前元素的索引标记为您弹出的每个索引的解决方案。
  • 将当前元素的索引压入堆栈。

不变量：栈中索引对应的数组项总是升序排列，最少的项在最上面。

当您到达输入的开头时，用 -1 标记仍然保留在堆栈中的任何项目；对他们来说没有答案。

每个数组索引只被压入堆栈一次，最多弹出一次，因此该算法在 O(n) 时间内运行。

Python中的一个例子： 

def solution(arr):
    stack = []
    out = [-1]*len(arr)
    for i in xrange(len(arr)-1, -1, -1):
        while len(stack) > 0 and arr[stack[-1]] < arr[i]:
            out[stack.pop()] = i
        stack.append(i);
    return out

请注意，输入的正确答案[2, 4, 1, 5, 3]是[-1, -1, 1, -1, 3]：对于固定的 i，当 j 最大时，差异 ji 最大，因此您正在寻找最左边的索引 j，它使距离最小化。（当 j < i 时，差 ji 为负。）

于 2013-10-14T09:35:03.513 回答
0

我能想到的最快的解决方案是分配第二个数组并从左到右扫描数组。当您遍历数组并扫描每个元素时，如果 arr[index] 大于第二个数组的最右侧元素，则将该元素的索引附加到第二个数组。这是每个追加的 O(1) 时间，最多 n 个追加，所以 O(n)。

最后，一旦您的阵列完成，请再次通过您的阵列。对于每个元素，使用二进制搜索扫描第二个数组（这是可能的，因为它是隐式排序的）并找到数组中最左边（最早插入）的索引 j，使得 arr[j] > arr[i]。

为此，您必须对二分搜索进行修改。如果你找到一个索引 j 使得 arr[j] > arr[i]，你仍然需要检查左边是否有任何索引 k 使得 arr[k] > arr[i]。您必须这样做，直到找到最左边的索引。

我认为这是每个二进制搜索的 O(log n)，你必须搜索 n 个元素。所以总时间复杂度将接近 O(n log n)，但我不确定这一点。对此答案的任何评论/建议将不胜感激。

于 2013-10-14T08:49:03.160 回答
0

这是我在 C++ 中的解决方案
我们维护一个不断增加的数组。将当前元素与数组后面的元素进行比较。如果它大于或等于到目前为止的最大元素，则将此元素附加到数组中，返回-1，它的左边没有更小的元素。

如果不是，我们使用二分查找，找到索引并返回差值。（我们仍然需要将 vec.back() 附加到数组中，因为我们无法更改索引）

int findIdx(vector<int>& vec, int target){
    auto it = upper_bound(vec.begin(), vec.end(), target);
    int idx = int(it-vec.begin());
    return idx;
}

vector<int> farestBig(vector<int>& arr){
    vector<int> ans{-1};
    vector<int> vec{arr[0]};
    int n = (int)arr.size();
    for(int i=1; i<n; i++){
        if(arr[i] >= vec.back()){
            ans.push_back(-1);
            vec.push_back(arr[i]);
        }
        else{
            int idx = findIdx(vec, arr[i]);
            ans.push_back(i-idx);
            vec.push_back(vec.back());
        }
    }
    return ans;
}
于 2020-01-31T22:39:49.767 回答