BiruLyu
8/10/2017 - 5:11 PM

334. Increasing Triplet Subsequence(#).java

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }
        int triplet1 = Integer.MAX_VALUE;
        int triplet2 = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= triplet1) {
                triplet1 = nums[i];
            }
            else if (nums[i] <= triplet2) {
                triplet2 = nums[i];
            }
            else {
                return true;
            }
        }
        return false;
    }
}
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) small = n;
            else if (n <= big) big = n;
            else return true;
        }
        return false;
    }
}
public class Solution {
    
    public boolean increasingTriplet(int[] nums) {
        int[] res = new int[3];
        int end = 0;
        for (int num : nums) {
            if(end == 0 || num > res[end - 1]) {
                res[end++] = num;
                if (end == 3) return true;
            } else {
                int i = 0;
                int j = end - 1;
                while (i < j) {
                    int mid = i + (j - i) / 2;
                    if (res[mid] < num) {
                        i = mid + 1;
                    } else {
                        j = mid;
                    }
                }
                res[i] = num;
            }
        }
        return false;
    }
}