LeetCode 334 递增的三元子序列

1.这个题看的题解

class Solution { public boolean increasingTriplet(int[] nums) { if(nums.length<3) return false; int small=Integer.MAX_VALUE,mid=Integer.MAX_VALUE; for(int i=0;i<nums.length;i++){ if(nums[i]<small){ small=nums[i]; }else if(nums[i]<mid&&nums[i]!=small){ mid=nums[i]; }else if(nums[i]>mid){ return true; } } return false; } }

class Solution { public boolean increasingTriplet(int[] nums) { if(nums.length<3) return false; int small=Integer.MAX_VALUE,mid=Integer.MAX_VALUE; for(int i=0;i<nums.length;i++){ if(nums[i]<=small){ small=nums[i]; }else if(nums[i]<=mid){ mid=nums[i]; }else{ return true; } } return false; } }

这上面两种就是判断方法不同，但是在时间复杂度差很多

1.维持的两个变量 small就是在标志着三元序列中的最小数，mid标志着三元序列中的中间那个数

2.遇到比small小或者等于的就更新small ，如果比small大比mid小或者等于mid，也更新mid，

3.我觉得一般都会有个疑惑，当你在mid之后更新small还能维持他们的递增序列i<j么？

我才开始也不理解 举个例子，5,7,2,1,9 看这个序列，small=5，mid=7，即便你的small更新为1，但是还是能说明mid是7

因为只要你曾经更新mid为7就说明，你在更新mid=7,你进了第一个if发现它比small大，说明存在这个数