Increasing Triplet Subsequence

Description

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

Solution(javascript)

/** 1. 双指针，最大值以及最小值，中间找一个值满足 min < middle < max 即可，好像有点问题
 * 比如：8 7 6 5 6 3 6 3 2 1 或者 5 6 1 2 3 6
 * 2. 也可以用单调栈来做，但是需要 O(N) Space， 也不行啊 0 10 0 100
 * 3. 模拟单调栈 不行
 * 4. 确定两个数更新第三个数
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) { 
    let a = Infinity
    let b = Infinity
    for(let num of nums) {
        if(num <= a) {
            a = num
        } else if(num <= b) {
            b = num
        } else {
            return true
        }
    }
    return false
};