每天一道算法题递增的三元子序列
递增的三元子序列
给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
示例:输入:nums = [2,1,5,0,4,6] 输出:true 解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
思考:
可以使用贪心的方法将空间复杂度降到 O(1)。从左到右遍历数组 nums,遍历过程中维护两个变量 first 和 second,分别表示递增的三元子序列中的第一个数和第二个数,任何时候都有 first second){ return true; } //如果值比first大,就把这个值赋值给second //这样second肯定在first后面 else if(num > first){ second = num; } //如果值比first还小,就把这个值赋值给first //此时这个值可能在second后面,但second前面肯定有一个值比他小 else { first = num; } } return false; }
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums 的长度。需要遍历数组一次。
空间复杂度:O(1)。