数组中大于给定数字的最大距离

Question

我正在处理一个面试问题...需要找到以下逻辑：

寻找一个索引`j`，使得元素`a[j]`大于`a[i]`（且`j

我现在所做的是：

1）通过简单的`for循环`使用`O(n^2)`。

2）从左到右扫描元素时构建平衡二叉搜索树，并为第`i`个元素找到大于它的元素的索引。但是我意识到它可以轻松地为单个元素使用`O(n)`，因此对于整个数组使用`O(n^2)`。

我想知道是否有可能在`O(n)`或`O(n log n)`的时间内完成。如果是，请给一些提示。

编辑：我认为我无法解释我的问题。让我清楚地解释一下：

我想要在`arr[i]`左侧找到`arr[j]`，使得`(i-j)`尽可能大，并且`arr[j]>arr[i]`，并为所有索引`i`找到这个值，即`for(i=0 to n-1)`。

编辑2：示例 - `{2,3,1,6,0}`

- 对于2，答案为-1 - 对于3，答案为-1 - 对于1，答案为2（`i-j==2-0`） - 对于6，答案为-1 - 对于0，答案为4（`i-j==4-0`）

- Aseem Goyal

---

你能举一个输入和输出数据的例子吗？ - Abhishek Bansal

我不太明白这个问题，是要找到数组中每个元素左侧最远的比当前元素大的元素吗？ - justhalf

我不确定我是否正确理解了意思，但这不是关于在数组中查找min和max，然后进行比较吗？即：[1. 查找min]; [2. 查找max]; [3. 对于给定的第i个元素，比较哪个更远 - min还是max]。就是这样。根据线性顺序的定义，没有什么可以更远了。 - Alma Do

arr[i] < arr[j] 并且最大化 arr[i]-arr[j] 的意思是你基本上在寻找比 arr[j] 更高的最接近的元素。这确实是这种情况吗？还是我误解了问题？ - amit

@all i-j 应该是最大值，而不是 arr[i]-arr[j]。 - Aseem Goyal

Answer 1

创建一个最大值辅助数组，将其命名为maxs，其中将包含到当前索引的数组中的最大值。

正式地说：maxs[i] = max { arr[0], arr[1], ..., arr[i] } 请注意，这是一个预处理步骤，可以在O(n)时间内完成。

现在，对于每个元素i，您要查找第一个在arr[i]之上的maxs元素。 这可以使用二分查找完成，并且每次操作的时间复杂度为O(logn)。

总时间复杂度为O(nlogn)，额外空间复杂度为O(n)。

- amit

---

你的解决方案有两个不清楚的地方：1. 如何在O(logn)时间内对最大数组应用二分查找？它可能看起来像[10, 10, 18, 24, 24, 24, 24, 24, 24]。2. 你的算法不完整 - 在查找第一个最大元素后，你需要将i-j的值（以及索引）存储在另一个数组中，并在最后找到该数组的最大值（或者在遍历最大数组时实时更新）。 - Ventsyslav Raikov

@amit，你错了，因为你只找到了max{arr[0],......arr[i-1]}，但是我们需要找到max(i-j)。 - Aseem Goyal

@anon 由于这是一个最大值数组，所以我们找到的元素保证是第一个大于arr[i]的元素 - 这意味着它也最大化了i-j，因为没有比j更小的元素高于arr[i]。 - amit

@amit 我明白你想要解释的内容。我无法分析二分查找。你是指像这样吗？ 我假设在maxs[i] = 最大元素的索引，而不是最大元素，target是arr[i]。bin_srch(start,end) { if(end<start) return -1 if(arr[end]<target) return -1 if(arr[start]>target) return start if(arr[mid]>target && mid-1>0 && arr[mid-1]>target) bin_srch(start,mid-1) else if(arr[mid]>target) return mid else return bin_srch(mid+1,end) } - Aseem Goyal

@anon 我觉得你的代码很难理解，二分查找是一个众所周知的算法，请参考维基百科文章。 - amit

Answer 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最大时，差值j-i最大，因此您要寻找最左边的索引j，使得距离最小化。 （当j < i时，差值j-i为负数。）

- Joni

---

哦，是的。刚意识到“最大的j-i”并不是最大的距离，而是最小的距离。需要明确与OP澄清，他到底想要最大的距离还是最大的j-i。 - justhalf

抱歉，在编辑帖子时犯了错误。真正的问题是“最大的i-j”。非常抱歉给您带来麻烦。 - justhalf

Answer 3

我能想到的最快解决方案是分配第二个数组并从左到右扫描该数组。当您遍历数组并扫描每个元素时，如果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)，但我不确定。对此答案的任何评论/建议将不胜感激。

- Shashank

---

你正在将arr[index]的值与第二个数组中包含的索引的最右边的元素进行比较。所以你是在比较一个元素和一个索引？还是你想要将其与第二个数组中最右边的元素指向的元素进行比较？ - justhalf

Answer 4

这是我的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;
}

- Jason Hou