Middle-タイトル44:344.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. 増加した長さ3のサブシーケンスが存在するか否かを判断する配列を与える.テーマ分析:(1)素朴解法:O(n 3)暴力捜索;(2)最長増分子列:Middle-題目33の手法を引用して最長増分子列の長さが>=3であるか否かを判断し,最適な時間複雑度はO(nlogn)である.(3)O(n)アルゴリズム:a 1が現在の最小値,a 2がa 1以降の小値となるように配列を1回走査すると,現在の数がa 2よりも大きくなると存在する.ソース:(language:java)

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int a1 = Integer.MAX_VALUE,a2 = Integer.MAX_VALUE;
        for(int num : nums) {
            if(num<=a1) 
                a1=num;
            else if(num<=a2)
                a2=num;
            else
                return true;
        }
        return false;
    }
}

成績:1 ms,beats 34.32%,衆数1 ms,65.68%