【每天学习一点算法 2026/03/03】递增的三元子序列

每天学习一点算法 2026/03/03

题目：递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvvuqg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1. 我们可以遍历数组查看左边变是否有小于自己的数以及右边是否有大于自己的数。

   functionincreasingTriplet(nums:number[]):boolean{for(leti=1;i<nums.length-1;i++){if(findLeft(i)&&findRight(i))returntrue}returnfalsefunctionfindLeft(index:number):boolean{returnMath.min(...nums.slice(0,index+1))<nums[index]}functionfindRight(index:number):boolean{returnMath.max(...nums.slice(index))>nums[index]}};

   这个方法很容易想到，但是遇到较长的测试用例就会超时。

   我们换一个思路，我们先维护两个数组leftMin和rightMax分别记录nums每个下标左侧范围最小数和右侧范围内最大的数，这样我们左右查找的循环操作只用做一次，后续遍历数组比较元素两侧最小值即可。

   functionincreasingTriplet(nums:number[]):boolean{constn=nums.length;if(n<3){returnfalse;}constleftMin=newArray(n).fill(0);leftMin[0]=nums[0]for(leti=1;i<n;i++){leftMin[i]=Math.min(nums[i],leftMin[i-1])}constrightMax=newArray(n).fill(0);rightMax[n-1]=nums[n-1]for(leti=n-2;i>=0;i--){rightMax[i]=Math.max(nums[i],rightMax[i+1])}for(leti=1;i<n-1;i++){if(nums[i]>leftMin[i-1]&&nums[i]<rightMax[i+1])returntrue}returnfalse};

2. 贪心算法

   我们可以维护两个变量first和second表示三元序列的第一个数和第二个数，遍历过程我们使first和second始终保持最小，这样就可以找出三元序列了。

   设定first和second初始值：

   first = nums[0]

   second = Infinity

   我们在遍历的过程中会遇到三种情况：

   • first < nums[i] < second时，需要替换second为nums[i]。
   • nums[i] < first时，需要替换first为nums[i]。
   • nums[i] > second时，我们就找到了第三个数。

   functionincreasingTriplet(nums:number[]):boolean{constn=nums.length;if(n<3){returnfalse;}letfirst=nums[0]letsecond=Infinityfor(leti=1;i<n;i++){if(nums[i]>second){returntrue}elseif(nums[i]>first){second=nums[i]}else{first=nums[i]}}returnfalse};

题目来源：力扣（LeetCode）