找出一个给定序列的子序列的最快方法是什么?它之前的每个元素都小于，之后的每个元素都大于
找出一个给定序列的子序列的最快方法是什么?它之前的每个元素都小于，之后的每个元素都大于
提问于 2019-06-05 08:03:05
对于给定序列中的每个元素x，在x之前的给定序列中的每个元素小于x，并且在x之后的给定序列中的每个元素大于x的条件下，找到给定序列的子序列的最快方法是什么
样本输入
9, 8, 7, 6, 5, 8, 9, 10, 11, 12, 10, 5, 2, 20, 25, 30, 80, 90, 100, 50, 40, 41样本输出
20, 25, 30回答 1
Stack Overflow用户
回答已采纳
发布于 2019-06-05 08:18:58
从你的序列开始，在左边构造最大值，在右边构造最小值：
9, 8, 7, 6, 5, 8, 9, 10, 11, 12, 10, 5, 2, 20, 25, 30, 80, 90, 100, 50, 40, 41
9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 12, 12, 12, 20, 25, 30, 80, 90, 100, 100, 100, 100
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 20, 25, 30, 40, 40, 40, 40, 40, 41取出三个数组匹配的数组。在本例中为20, 25, 30。
这需要时间和内存O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56452743
复制相关文章
相似问题