【LeetCode】- Java - 递增的三元子序列

水深无声 2022-02-09 08:53 186阅读 0赞

题目描述：

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的**递增子序列**。

数学表达式如下:

> 如果存在这样的 *i, j, k,*  且满足 0 ≤ *i* < *j* < *k* ≤ *n*\-1，  
> 使得 *arr\[i\]* < *arr\[j\]* < *arr\[k\]* ，返回 true ; 否则返回 false 。

**说明:** 要求算法的时间复杂度为 O(*n*)，空间复杂度为 O(*1*) 。

**示例 1:**

>     输入: [1,2,3,4,5]
>     输出: true

**示例 2:**

>     输入: [5,4,3,2,1]
>     输出: false

方法一：抛开说明，先定义一个数组dp并初始化为1，dp\[i\]表示在i位置之前小于nums\[i\]的数字的个数(包括其本身)，代码如下：

private static boolean increasingTriplet(int[] nums) {
    		// 定义一个数组存储第i个位置比i小的元素的个数，包括第i个元素本身
    		int[] dp = new int[nums.length];
    
    		// 初始化为1
    		int i = 0;
    		while (i < nums.length) {
    			dp[i++] = 1;
    		}
    
    		for (i = 0; i < nums.length; ++i) {
    			for (int j = 0; j < i; ++j) {
    				if (nums[j] < nums[i]) {
    					
    					dp[i] = Math.max(dp[i], dp[j] + 1);
    					
    					// 如果找到第i个位置前面已经有3个元素小于当前元素，则直接终止
    					if (dp[i] >= 3)
    						return true;
    				}
    			}
    		}
    		return false;
    	}

方法二：定义两个变量first和second分别存储，三元递增序列的最小值和次小值，当读到第三个值如果大于次小值，说明存在3元递增序列，代码如下：

private static boolean increasingTriplet(int[] nums) {
    		int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
    		for (int a : nums) {
    			if (first >= a) {
    				first = a;
    			} else if (second >= a) {
    				second = a;
    			} else
    				return true;
    		}
    		return false;
    	}

参考资料 ：[https://leetcode-cn.com/problems/increasing-triplet-subsequence/comments/][https_leetcode-cn.com_problems_increasing-triplet-subsequence_comments]

[https_leetcode-cn.com_problems_increasing-triplet-subsequence_comments]: https://leetcode-cn.com/problems/increasing-triplet-subsequence/comments/