LeetCode(Array&String)Increasing Triplet Subsequence

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.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

思路：因为i,j,k不一定是连续的，所以，能想到的就是三个for循环嵌套，才能遍历所有可能的结果，但是这样计算量就很大。必须想办法减少其中的计算量，我们定义了一个辅助的boolean矩阵flag[i]来记录数组中以第i个数字开头是否满足一个三个连续子序列递增的条件，如果满足就返回true，不满足就返回false，给i++的判断提供依据，减少计算量。

代码如下：

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int len=nums.length;
        if(len<3){
            return false;
        }
        boolean [] flag=new boolean [len];
        for(int i=0;i+2<len;i++){
            if(i>0 && flag[i-1]==false && nums[i]>nums[i-1]){
                continue;
            }
            for(int j=i+1;j<len;j++){
                if(nums[i]>=nums[j]){
                    flag[i]=false;
                    continue;
                }
                for(int k=j+1;k<len;k++){
                    if(nums[i]<nums[j] && nums[j]<nums[k]){
                        flag[i]=true;
                        return true;
                    }else{
                        flag[i]=false;
                    }
                }
            }
        }
        return false;
    }
}