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

摆动序列

• 摆动序列

贪心策略：统计出所有的极大值和极小值，以及最前和最后的两个点。

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;
    }
};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~