给定一个整数向量，我需要找出是否存在三个元素 a, b, c在向量中 a < b< c和 v[a] < v[c] < v[b] .
到目前为止，我的方法如下。首先，我忘记了 a 并为向量中的每个数字找到位于该元素左侧的 v[i] 的最小值。我将此信息存储在另一个数组中。然后我应用合并排序，当我到达两个元素交叉的点时，我测试右边的元素是否可以是 c 而左边的元素是 b。但是，我还需要测试与正确元素交叉的其他元素是否可以是b，这增加了太多的时间复杂度。我最多需要它是线性的。 你能给我一个关于如何继续的提示吗？
编辑:请原谅，之前的标题不对。我需要的是 a < b < c 和 v[a] < v[c] < v[b]
EDIT2: 限制:除了向量之外，我不能使用数据结构。并且算法必须基于分而治之的方法。
最佳答案
您可以在 O(n) 时间和最坏的 O(n) 时间内完成此操作通过遍历数组同时维护最大禁止范围(v[a]、v[c])的堆栈(后进先出数据结构)。堆栈的最顶层元素是从目前看到的最小值到该最小值之后看到的最大值的范围。 (或者，出于实现原因，您可能会发现将该范围保存在单独的变量中更容易，并且仅将堆栈用于旧禁止范围。)
处理任何单个元素最多可能需要 O(n) 时间(如果它必须展开整个堆栈一直回到第一个范围)，但是这个成本必须摊销，这样处理整个数组仍然只有 O(n) 时间(因为处理一个元素会展开整个堆栈的唯一原因是如果它将所有禁止范围统一为一个更大的范围，在这种情况下，它不需要重新添加它弹出的所有范围，因此该工作仅完成一次) .
关于在数组中查找三个数字的算法，使得 a< b < c 和 v[a]<v[c]<v[b]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53583796/