内容纲要
题目链接
题目描述:给你一个整数数组nums
,判断这个数组中是否存在长度为3
的递增子序列。
注意:如果存在这样的三元组下标(i, j, k)
且满足i < j < k
,使得nums[i] < nums[j] < nums[k]
,返回true
;否则,返回false
。
示例1:
输入:nums = [1, 2, 3, 4, 5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
示例2:
输入:nums = [5, 4, 3, 2, 1]
输出:false
解释:不存在满足题意的三元组
示例3:
输入:nums = [2, 1, 5, 0, 4, 6]
输出:true
解释:三元组(3, 4, 5)
满足题意,因为nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示:
1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1
进阶:你能实现时间复杂度为O(n)
,空间复杂度为O(1)
的解决方案吗?
解法一:双向遍历
解析
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
if (n < 3) return false;
// lmin[i]:表示nums[0]到nums[i]中的最小值;
// rmax[i]:表示nums[i]到nums[n-1]中的最大值。
int lmin[n], rmax[n];
lmin[0] = nums[0];
for (int i = 1; i < n; i++) lmin[i] = min(lmin[i - 1], nums[i]);
rmax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) rmax[i] = max(rmax[i + 1], nums[i]);
for (int i = 1; i < n - 1; i++)
if (lmin[i - 1] < nums[i] && nums[i] < rmax[i + 1])
return true;
return 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 x : nums) {
if (x <= first) first = x;
else if (x <= second) second = x;
else return true;
}
return false;
}
};
测试评论~:penguin::laughing:
:smiley: