334 Increasing Triplet Subsequence 递增的三元子序列

给定一个未排序的数组,请判断这个数组中是否存在长度为3的递增的子序列。
正式的数学表达如下:
    如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1,
    使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
要求算法时间复杂度为O(n),空间复杂度为O(1) 。
示例:
输入 [1, 2, 3, 4, 5],
输出 true.
输入 [5, 4, 3, 2, 1],
输出 false.

详见:https://leetcode.com/problems/increasing-triplet-subsequence/description/

C++:

方法一:超时

class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,1);
for(int i=0;i<n;++i)
{
for(int j=0;j<i;++j)
{
if(nums[j]<nums[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
if(dp[i]>=3)
{
return true;
}
}
}
return false;
}
};

方法二:

使用两个指针m1和m2,初始化为整型最大值,遍历数组,如果m1大于等于当前数字,则将当前数字赋给m1;如果m1小于当前数字且m2大于等于当前数字,那么将当前数字赋给m2,一旦m2被更新了,说明一定会有一个数小于m2,那么就成功的组成了一个长度为2的递增子序列,所以一旦遍历到比m2还大的数,直接返回ture。如果遇到比m1小的数,还是要更新m1,有可能的话也要更新m2为更小的值,毕竟m2的值越小,能组成长度为3的递增序列的可能性越大。

class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int m1=INT_MAX,m2=INT_MAX;
for(int a:nums)
{
if(m1>=a)
{
m1=a;
}
else if(m2>=a)
{
m2=a;
}
else
{
return true;
}
}
return false;
}
};

参考:https://www.cnblogs.com/grandyang/p/5194599.html

上一篇:Linux重启服务器步骤


下一篇:334. Increasing Triplet Subsequence