在数组中查找三个数字的算法，使得 a< b < c 和 v[a]<v[c]<v[b]
Algorithm to find three numbers in an array such that a< b < c and v[a]<v[c]<v[b]
给定一个整数向量，我需要找出向量中是否存在三个元素 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) 额外 space 通过遍历数组同时维护最大禁止范围的堆栈（后进先出数据结构）（v[a]，v[c] ).堆栈的最顶层元素是从目前看到的最小值到该最小值之后看到的最大值的范围。 （或者，出于实现的原因，您可能会发现将该范围保存在单独的变量中更容易，并且仅将堆栈用于 older 禁止范围。）
处理任何单个元素最多可能需要 O(n) 时间（如果它必须一直展开整个堆栈回到第一个范围），但这个成本必须摊销，这样处理整个数组仍然只有 O(n) 时间（因为处理一个元素会展开整个堆栈的唯一原因是它是否将所有禁止范围统一为一个更大的范围，在这种情况下它不需要重新添加它弹出的所有范围，所以这项工作只完成了 一次).
给定一个整数向量，我需要找出向量中是否存在三个元素 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) 额外 space 通过遍历数组同时维护最大禁止范围的堆栈（后进先出数据结构）（v[a]，v[c] ).堆栈的最顶层元素是从目前看到的最小值到该最小值之后看到的最大值的范围。 （或者，出于实现的原因，您可能会发现将该范围保存在单独的变量中更容易，并且仅将堆栈用于 older 禁止范围。）
处理任何单个元素最多可能需要 O(n) 时间（如果它必须一直展开整个堆栈回到第一个范围），但这个成本必须摊销，这样处理整个数组仍然只有 O(n) 时间（因为处理一个元素会展开整个堆栈的唯一原因是它是否将所有禁止范围统一为一个更大的范围，在这种情况下它不需要重新添加它弹出的所有范围，所以这项工作只完成了 一次).