给定一个未排序的数组,判断这个数组中是否存在长度为 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

暴力破解法,时间耗费的是 O(N*N*N)。如果是需要找递增的二元组的话完全可以使用 O(N)的遍历方法,但是在解题中,第二个数和第三个数进行对比的前提是第二个数大于第一个数,而这个前提又是基于对数组的遍历,所以形成了 O(N*N*N)。
可以想到的优化是第一个循环用来一边遍历一边对比,对比为真时再进入下一个循环,这时的空间复杂度为 O(N*N)
如果不想嵌套下一个循环的,可以使用数组将比较完成的状态进行存储。另开一个循环,对比遍历时使用数组中的数据得出结果,这种方法的空间复杂度是O(N)。

空间复杂度O(1)的思路有点类似动态规划的思想,维护一个二元组(first,second),记录第i个元素之前的“最小”递增二元子序列(对后续元素的要求最低如[5,6,2,3,4]会更新[5,6]为[2,3]此时只要后续满足大于3就可以)
当nums[i]小于first时,更新first的值
当nums[i]>first且nums[i]

//O(n) public static boolean increasingTriplet(int[] arr) { if(arr.length <= 2) return false; int n = arr.length; boolean[] hasfirstsmall = new boolean[n]; int smallest = arr[0]; hasfirstsmall[0] = false; for(int i = 0;i=0;i--) { if(hasfirstsmall[i] == true) { if(arr[i] < biggest) return true; biggest = Math.max(biggest, arr[i]); } } return false; } //O(1) public static boolean increasingTriplet2(int[] arr) { if(arr.length <= 2) return false; int first = Integer.MAX_VALUE; int second = Integer.MAX_VALUE; for(int i = 0;i first && arr[i] <= second) { second = arr[i]; continue; } if(arr[i] > second) { return true; } } return false; }