算法：找出数组中比左边大比右边小的元素

题目：以时间复杂度 O(n) 从长度为n的数组中找出同时满足以下两个条件的所有元素：

1. 该元素比放在它左边所有的元素都要大；
2. 该元素比放在它右边所有的元素都要小；

示例：

输入：[1, 2, 4, 3, 5, 9]
输出：[2, 5]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var res = function(nums) {

};

解题思路：

1. 由于限制了时间复杂度为O(n)，因此不能用嵌套循环的方法
2. 首先倒序（从右往左）遍历，找到当前 index 右边所有元素中的最小值
3. 然后正序（从左往右）遍历，判断当前元素是否为它左边所有元素的最大值，如果满足条件，最后再跟当前 index 右边的最小值对比，获取符合条件的元素。

// code：
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var res = function(arr) {
    if (arr.length < 3) {
        return [];
    }
    const res = [];
    const m = new Array(arr.length);
    let min = arr[arr.length - 1];
    // 先生成一个新数组，每个位置的值表示它右边做小的值（不包含它本身）
    for(let i = arr.length - 2; i > 0; i--) {
        m[i] = min;
        if (arr[i] < min) {
            min = arr[i];
        }
        m[i - 1] = min;
    };
    console.log(m);
    let max = arr[0];
    for(let i = 1; i < arr.length - 1; i++) {
        // 如果当前值是比它前面最大的值还要大
        if (arr[i] > max) {
            max = arr[i];
            // 并且比它右边最小的值还要小，则满足条件
            if (arr[i] < m[i]) {
                res.push(max);
            }
        }
    }
    return res;
}