当前位置：首页 > web >正文

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

web 2025/5/4 10:55:19

⭐️个人主页：@小羊 ⭐️所属专栏：贪心算法很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

摆动序列

摆动序列

在这里插入图片描述

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

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