leetcode 334. Increasing Triplet Subsequence 自增序列3个元素 + 动态规划DP + 一个很很简单的想法

阳光穿透心脏的1/2处 2022-06-07 01:13 111阅读 0赞

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.  
Your algorithm should run in O(n) time complexity and O(1) space complexity.

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

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

最容易想起的方法就是LISS最长递增序列的DP求解方法，不过题目要求 O(n) time complexity and O(1) space complexity 所以和这个方法肯定不合适

本题可以用最长升序子序列的方法来做，但是有点小题大做了。还可以维护一个当前的长度为2的升序序列(小的值叫small, 大的叫big)，如果碰到比第二个值大的说明可以找到升序的三个值。并且在过程中不断更新small和big的值，使得他们最小。

说实话，没有想到还有这么简单的方法，网上看到了一个答案，才知道自己是多么的愚蠢，这道题很值得学习。

代码如下：

import java.util.Arrays;
    
    
    /*
     * 最容易想起的方法就是LISS最长递增序列的DP求解方法
     * 不过题目要求 O(n) time complexity and O(1) space complexity
     * 所以和这个方法肯定不合适
     * 
     * 本题可以用最长升序子序列的方法来做，但是有点小题大做了。
     * 还可以维护一个当前的长度为2的升序序列(小的值叫small, 大的叫big)，
     * 如果碰到比第二个值大的说明可以找到升序的三个值。并且在过程中不断更新small和big的值，
     * 使得他们最小。
     * */
    public class Solution 
    {
        
        public boolean increasingTriplet(int[] nums)
        {
            if(nums==null || nums.length<=2)
                return false;
    
            int small=Integer.MAX_VALUE;
            int large=Integer.MAX_VALUE;
            for(int i=0;i<nums.length;i++)
            {
                if(nums[i]<=small)
                    small=nums[i];
                else if(nums[i]<=large)
                    large=nums[i];
                else
                    return true;
            }   
            return false;
        }
    
        /*
         * DP 对于本题大题小做了
         * */
        public boolean increasingTriplet111111(int[] nums)
        {
            if(nums==null || nums.length<=2)
                return false;
    
            int []len=new int[nums.length];
            Arrays.fill(len, 1);
    
            for(int i=1;i<nums.length;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(nums[j]<nums[i] && len[j]+1 > len[i])
                        len[i]=len[j]+1;                    
                }
                if(len[i]>=3)
                    return true;
            }   
            return false;
        }
    
        public static void main(String[] args)
        {
            Solution solution=new Solution();       
            int[]nums={
       1,2,3,4,5,6};
            System.out.println(solution.increasingTriplet(nums));
        }
    }

下面是C++的做法

最简单的最直接的方法就是使用LISS最长递增子序列，但是会超时，后来看到了一个十分简单的方法，真心的是十分棒，很值得反思和学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        bool increasingTriplet(vector<int>& nums)
        {
            if (nums.size() <= 2)
                return false;
            int firstSmall = INT_MAX, secSmall = INT_MAX;
            for (int i : nums)
            {
                if (i <= firstSmall)
                    firstSmall = i;
                else if (i <= secSmall)
                    secSmall = i;
                else
                    return true;
            }
            return false;
        }
    
    
        bool increasingTripletByDP(vector<int>& nums)
        {
            vector<int> dp(nums.size(), 1);
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[j]<nums[i] && dp[j] + 1>dp[i])
                        dp[i] = dp[j] + 1;
                }
                if (dp[i] >= 3)
                    return true;
            }
            return false;
        }
    };