Array - 334. Increasing Triplet Subsequence

334. 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.

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

Example 1:

Input: [1,2,3,4,5] Output: true

思路：

这道题可以用动态规划来做，记录每一位为止的最长子序列的长度。时间复杂度和空间复杂度都是O(n), 当然也可以把空间复杂度优化成O(1)，也就是只记录两位。但是这题我选择greedy来做。

代码：

class Solution {

    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length <= 2) return false;
        
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        
        for (int num : nums) {
            if (num > min2) {
                return true;
            } else if (num < min1) {
                min1 = num;
            } else if (num > min1 && num < min2) {
                min2 = num;
            }
        }
        
        return false;
    }
}