leetcode-递增的三元子序列

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

思路：

实际参考思路是：先找到一个长度为2的递增序列，然后继续遍历找到一个比数组最大值更大的数字。 因此该过程中需要记录数组。 采用分别处理，如果有一个长度为2的递增序列，那么记录数组下标为true，同时更新最大值。 这种算法的空间复杂度是o(n)。 友情提示：一定是取得最大值和最小值去比较，只要有比最小值小，比最大值大的数，那么记录下来的数组就为true。

class Solution {    public boolean increasingTriplet(int[] nums) {       if(nums.length<3)return false;int smallest=nums[0];        boolean uper[]=new boolean[nums.length];              //利用数组记录长度为2的递增序列          for(int i=1;i){            if(nums[i]>smallest){                uper[i]=true;              }            smallest=Math.min(smallest,nums[i]);        }            int biggest=nums[nums.length-1];//再次遍历数组，此次从最后开始，不断更新最大值，只要满足长度为2的递增序列，同时当前遍历数字小于最大值，则返回true            for(int i=nums.length-2;i>=0;i--){                    //遍历是从倒数第二个数字开始的                if(nums[i]<biggest){                    if(uper[i]==true)return true;                }                biggest=Math.max(nums[i],biggest);            }        return false;    }}

空间复杂度O(1)的解法：

思路：

首先设置m1,m2为Int最大值，然后对遍历的每一个数进行比较，m1记录数组中的最小值，m2记录比m1大的数字。 继续遍历，只要找到一个比m1,m2都更大的数字，那么返回true。

以及注意这个if语句的划分范围。

class Solution {    public boolean increasingTriplet(int[] nums) {       if(nums.length<3)return false;        int m1=Integer.MAX_VALUE,m2=Integer.MAX_VALUE;        for(int i=0;i){ //这里使用的是if (){}else if() { }  else 语句，判断的逻辑是一开始是更新m1,m2,遍历两个数字时m1            if(m1>=nums[i])m1=nums[i];                                    else if(m2>=nums[i])m2=nums[i];            else return true;        }        return false;    }}

在更新过程中也可使用此种逻辑表示：

 if(nums[i]<=m1){                 m1 =nums[i];                 continue;             }             if(m1m2){                 m2 =nums[i];                 continue;             }             if(nums[i]>m2){                 return true;             

总结：这道题的难点在于if else if语句的逻辑掌握和难以想到用两个数字代替一个递增序列的情况。