Increasing Triplet Subsequence 递增的三元子序列 (Medium)

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.

Example:

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

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

Analysis

This problem can be converted to be finding if there is a sequence such thatthe_smallest_so_far < the_second_smallest_so_far < current. We use x, y and z to denote the 3 number respectively.

public boolean increasingTriplet(int[] nums) {
    int x = Integer.MAX_VALUE;
    int y = Integer.MAX_VALUE;

    for (int i = 0; i < nums.length; i++) {
        int z = nums[i];

        if (x >= z) {
            x = z;// update x to be a smaller value
        } else if (y >= z) {
            y = z; // update y to be a smaller value
        } else {
            return true;
        }
    }

    return false;
}