September 08, 2019

334. Increasing Triplet Subsequence

DP

此解法不符合题目条件 Your algorithm should run in O(n) time complexity and O(1) space complexity. Time = O(n^2), Space = O(1)

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        int[] increasingTriplet = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            increasingTriplet[i] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j --) {
                if (nums[j] < nums[i]) {
                    increasingTriplet[i] = Math.max(increasingTriplet[i], increasingTriplet[j] + 1);
                    if (increasingTriplet[i] == 3) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

Greedy

因为题目要求 Triplet Subsequence，只需要保存最小的数和第二小的数。Time = O(n), Space = O(1)

class Solution {
    public boolean increasingTriplet(int[] nums) {

        int min1 = Integer.MAX_VALUE; // 当前最小的数
        int min2 = Integer.MAX_VALUE; // 当前第二小的数
        
        // loop 整个数组，不断更新当前最小和当前第二小的数
        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;
    }
}