algorithm - 在数组中找到三个数字的算法，使得 a< b < c 和 v[a]<v[c]<v[b]< h1=""> <div id="body"><p>给定一个整数向量，我需要找出向量中是否存在三个元素<code>a, b, c</code>，使得<code>a < b< c</code>和<code>v[a] < v[c] < v[b]</code>。</p> <p>到目前为止，我的方法如下。首先，我忘记了 a 并为向量中的每个数字找到位于该元素左侧的 v[i] 的最小值。我将此

给定一个整数向量，我需要找出向量中是否存在三个元素a, b, c，使得a < b< c和v[a] < v[c] < v[b]。

到目前为止，我的方法如下。首先，我忘记了 a 并为向量中的每个数字找到位于该元素左侧的 v[i] 的最小值。我将此,algorithm,vector,data-structures,divide-and-conquer"/>

首页 > 解决方案 > 在数组中找到三个数字的算法，使得 a< b < c 和 v[a]

给定一个整数向量，我需要找出向量中是否存在三个元素a, b, c，使得a < b< c和v[a] < v[c] < v[b]。

到目前为止，我的方法如下。首先，我忘记了 a 并为向量中的每个数字找到位于该元素左侧的 v[i] 的最小值。我将此

问题描述

给定一个整数向量，我需要找出向量中是否存在三个元素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], ) 的堆栈（LIFO 数据结构v[c]）。堆栈的最顶部元素是从迄今为止看到的最小值到自该最小值以来看到的最大值的范围。（或者，出于实现原因，您可能会发现将该范围保存在单独的变量中更容易，并且仅将堆栈用于较旧的禁止范围。）

处理任何单个元素最多可能需要O ( n ) 时间（如果它必须将整个堆栈一直展开回到第一个范围），但是这个成本必然是摊销的，因此处理整个数组仍然只有O ( n ) 时间（因为处理一个元素会展开整个堆栈的唯一原因是将所有禁止范围统一为一个更大的范围，在这种情况下，它不需要重新添加所有范围它弹出，所以工作只完成一次）。

标签： algorithmvectordata-structuresdivide-and-conquer

问题描述

解决方案

推荐阅读