334.递增的三元子序列

/**
 * @param {number[]} nums
 * @return {boolean}
 */
/**
 * 贪心算法
1.如果 num >second则找到了一个递增的三元子序列，返回true
2.否则，如果 num>first则将second的值更新为num
3.否则，将 first 的值更新为 num

如果遍历结束时没有找到递增的三元子序列，返回false

上述做法的贪心思想是：为了找到递增的三元子序列，first和second应该尽可能地小，此时找到递增的三元子序列的可能性更大。
 */
var increasingTriplet = function (nums) {
    let n = nums.length
    if (n < 3) {
        return false
    }

    let first = nums[0] // 第一个数
    let second = Infinity // 第二个数
    for (let i = 1; i < n; i++) {
        let num = nums[i]
        if (num > second) {
            return true
        } else {
            if (num > first) {
                second = num
            } else {
                first = num
            }
        }
    }
    return false
};

// 题目变换，遍历每个数的时候，看这个数之前有没有比它小的数，这个数后面有没有比它大的数
var increasingTriplet = function (nums) {
    let n = nums.length
    if (n < 3) {
        return false
    }
    let leftMin = new Array(n).fill(0)
    leftMin[0] = nums[0]
    for (let i = 1; i < n; i++) {
        // 第i个数的最小值(包括自己)
        leftMin[i] = Math.min(leftMin[i - 1], nums[i])
    }

    let rightMax = new Array(n).fill(0)
    rightMax[rightMax.length - 1] = nums[n - 1]
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], nums[i])
    }

    for (let i = 1; i < n - 1; i++) {
        // 不能这样写，时间复杂度过高，会超出时间限制，得提前求出每个数的最大最小值
        // let min = Math.min(...nums.slice(0, i))
        // let max = Math.max(...nums.slice(i + 1))
        // if (nums[i] > min && nums[i] < max) {
        //     return true
        // }
        if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
            return true
        }
    }
    return false
}

console.log(increasingTriplet([1, 5, 0, 4, 1, 3]))