arrays - 查找大于所有先前的数组元素

Question

我一直在努力解决的问题。给定一个数组:1 2 2 4 4 6 5 4 5 7 8 9 11 13找到第一个大于前面所有元素且小于前面所有元素的元素。我的想法是对数组进行排序，然后找到第一个没有改变其在数组中原始位置的元素。你怎么看？有人有更好的方法吗？

有没有办法在 O(N^2) 内完成？

谢谢

Answer 1

1. 从左到右扫描，跟踪当前最大值。标记当前最大值的任何元素。
2. 从右向左扫描，跟踪当前最小值。还跟踪当前最左边的标记元素，该元素也是当前最小值。

(感谢@Konstantinos 在下面的评论中提出优化建议。)

第 1 步找到所有满足第一个条件的元素，与第 2 步类似。整个事情在时间和空间上都是 O(n)。