// 题目:
// 以时间复杂度 O(n) 从长度为 n 的数组中找出同时满足下面两个条件的所有元素:
// (1)该元素比放在它前面的所有元素都大;
// (2)该元素比放在它后面的所有元素都小。
function smallLarge(arr) {
let len = arr.length
let res = []
let rMinArr = new Array(len) // 记录arr[i]右边(包括自己)的最小值
rMinArr[len - 1] = arr[len - 1]
for (let i = len - 2; i >= 0; i--) {
rMinArr[i] = arr[i] < rMinArr[i + 1] ? arr[i] : rMinArr[i + 1]
}
let lMax = arr[0] // 记录arr[i]左边(包括自己)的最大值
// 注意: 左右两边第一个数不满足条件
for (let i = 1; i < len - 1; i++) {
if (arr[i] > lMax) {
lMax = arr[i]
if (arr[i] < rMinArr[i + 1]) res.push(arr[i])
}
}
return res
}
let arr = [21, 11, 45, 56, 9, 66, 77, 89, 78, 68, 100, 120, 111]
console.log(smallLarge(arr))