【序列贪心】摆动序列 / 最长递增子序列 / 递增的三元子序列 / 最长连续递增序列

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        int ret = 0, left = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int right = nums[i + 1] - nums[i];// 计算接下来的趋势
            if (right == 0) continue;// 是否水平
            if (right * left <= 0) ret++;// 极大值或极小值
            left = right;// 更新趋势
        }
        return ret + 1; // 加上最后一个数
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> v;
        v.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] > v.back()) v.push_back(nums[i]);
            int l = 0, r = v.size() - 1; // 插在它刚好大过的数前面
            while (l < r)
            {
                int mid = (l + r) / 2;
                if (v[mid] < nums[i]) l = mid + 1;
                else r = mid;
            }
            v[l] = nums[i];
        }
        return v.size();
    }
};

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

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size(), ret = 0;
        for (int i = 0; i < n;)
        {
            int j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) j++;
            ret = max(ret, j - i);
            i = j;
        }
        return ret;
    }
};