力扣-334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

方法1：

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int main()
{
    int nums[] = {1,2,3,0,5};
    int n = sizeof(nums)/sizeof(nums[0]);
    bool flag = false;
    if (n < 3) {
        flag = false;
        cout<<flag<<endl;
        return 0;
    }
    vector<int> leftMin(n);
    leftMin[0] = nums[0];
    for (int i = 1; i < n; i++) {
        leftMin[i] = min(leftMin[i - 1], nums[i]);
    }
    vector<int> rightMax(n);
    rightMax[n - 1] = nums[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = max(rightMax[i + 1], nums[i]);
    }
    for (int i = 1; i < n - 1; i++) {
        if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
            flag = true;
            cout<<flag<<endl;
            return 0;
        }
    }
    flag = false;
    cout<<flag<<endl;
}

方法2：

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int main()
{
    int nums[] = {1,2,3,0,5};
    int n = sizeof(nums)/sizeof(nums[0]);
    if (n < 3) {
        cout<<"false"<<endl;
        return 0;
    }
    int first = nums[0];
    int second = INT_MAX;
    for (int i = 1; i < n; i++) {
        int num = nums[i];
        if (num > second) {
            cout<<"true"<<endl;
            return 0;
        } else if (num > first) {
            second = num;
        } else {
            first = num;
        }
    }
    cout<<"false"<<endl;
}

方法一：

时间复杂度为O(n)，空间复杂度也为O(n)，找一个数，他左边有一个值小于它，右边有一个数大于它

方法二：

时间复杂度为O(n)，空间复杂度也为O(1)
可以使用贪心的方法将空间复杂度降到 O(1)。
从左到右遍历数组 nums，遍历过程中维护两个变量 first和 second，分别表示递增的三元子序列中的第一个数和第二个数，任何时候都有 first < second。
初始时，first=nums[0]，second=+∞。对于 1≤i<n，当遍历到下标 i 时，令 num=nums[i]，进行如下操作：
如果 num>second，则找到了一个递增的三元子序列，返回 true；
否则，如果 num>first，则将 second的值更新为 num；
否则，将 first的值更新为 num。
如果遍历结束时没有找到递增的三元子序列，返回 false。