Leetcode/F家 -- 334. Increasing Triplet Subsequence (ini value)

334. Increasing Triplet Subsequence (初始值)
medium
https://leetcode.com/problems/increasing-triplet-subsequence/

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.

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

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

思路1： Iterate through the array, keep track the 2 min(so far) variables, initialize with Integer.MAX_VALUE to overwrite.
             If there is any element greater than firstMin and secondMin. We find answer.

Complexity: O(N)time O(1)space

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length<=2)return false;
        int firstMin = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        for(int n : nums){
            if(n <= firstMin){
                firstMin = n;
            }else if(n <= secondMin){
                secondMin = n; 
            }else{
                return true;
            }
        }
        return false;
    }
}

思路2： DP, 其实类似与 300. find longest increasing subsequence length 只要看max 有没有>=3