每天一道算法题递增的三元子序列
递增的三元子序列
给你一个整数数组nums,判断这个数组中是否存在长度为3的递增子序列。如果存在这样的三元组下标(i,j,k)且满足ijk,使得nums〔i〕nums〔j〕nums〔k〕,返回true;否则,返回false。
示例:输入:nums〔2,1,5,0,4,6〕输出:true解释:三元组(3,4,5)满足题意,因为nums〔3〕0nums〔4〕4nums〔5〕6
思考:
可以使用贪心的方法将空间复杂度降到O(1)。从左到右遍历数组nums,遍历过程中维护两个变量first和second,分别表示递增的三元子序列中的第一个数和第二个数,任何时候都有firstsecond。staticbooleanincreasingTriplet1(int〔〕nums){intnnums。length;先判断数组的长度if(n3){returnfalse;}设置递增的三元子序列中的第一个值,即数组的第一个值intfirstnums〔0〕;设置第二个值,整数最大值intsecondInteger。MAXVALUE;for(inti1;in;i){遍历每一个下标元素的值intnumnums〔i〕;当遍历到一个值比第二个大时,直接返回trueif(numsecond){returntrue;}如果值比first大,就把这个值赋值给second这样second肯定在first后面elseif(numfirst){secondnum;}如果值比first还小,就把这个值赋值给first此时这个值可能在second后面,但second前面肯定有一个值比他小else{firstnum;}}returnfalse;}
复杂度分析
时间复杂度:O(n),其中n是数组nums的长度。需要遍历数组一次。
空间复杂度:O(1)。