LeetCode 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

Example 2:

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

解析：

从未排序的数组中找到满足递增顺序的三元组。要求时间复杂度为O(n)，空间复杂的为O(1)

解法1：

动态规划法，令dp[i]表示以i元素结尾的递增序列长度。代码如下：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int len = nums.size();
        if(len < 3)
            return false;
        vector<int> dp(len, 1);
         //两重循环处理
        for(int i = 0; i < len; i++)
        {
            for(int j=0; j < i; j++)//遍历从首位置到当前元素的数字
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            if(dp[i] >= 3)
                return true;
        }
        return false;
    }
};

但是这样时间复杂度和空间复杂度均不满足要求。

解法2：

采用双指针法，两个指针x1和x2，作为最小和次小的候选。初始化为最大值，如果当前元素小于x1，则更新x1为当前元素；如果当前元素大于x1小于x2，则更新x2，此时已经存在2个数的递增序列。如果下一个元素大于x1和x2，则就构成了一个三元递增序列。代码如下：

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int x1=INT_MAX, x2=INT_MAX;
        for(auto& num : nums)
        {
            if(num <= x1)
                x1 = num;
            else if(num <= x2)
                x2 = num;
            else 
                return true;
        }
        return false;
    }
};

用时情况：

方法1 和方法2 的时间对比如下：

参考：

https://leetcode.com/problems/increasing-triplet-subsequence/discuss/78993/Clean-and-short-with-comments-C%2B%2B

cnblogs.com/grandyang/p/5194599.html