一、题目
给你一个整数数组 nums
,判断这个数组中是否存在长度为 3
的递增子序列。
如果存在这样的三元组下标 (i, j, k)
且满足 i < j < k
,使得 nums[i] < nums[j] < nums[k]
,返回 true
;否则,返回 false
。
二、思路
三、代码
class Solution { public: bool increasingTriplet(vector<int>& nums) { int n = nums.size(); if (n < 3) { return false; } int first = nums[0], second = INT_MAX; for (int i = 1; i < n; i++) { int num = nums[i]; if (num > second) { return true; } else if (num > first) { second = num; } else { first = num; } } return false; } };
四、分析
复杂度分析
时间复杂度:O(n),其中 nnn 是数组 nums 的长度。需要遍历数组一次。
空间复杂度:O(1)。