??個人主頁：@小羊 ??所屬專欄：貪心算法 很榮幸您能閱讀我的文章，誠請評論指點，歡迎歡迎 ~

---

擺動序列

• 擺動序列

貪心策略：統計出所有的極大值和極小值，以及最前和最后的兩個點。

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

---

本篇文章的分享就到這里了，如果您覺得在本文有所收獲，還請留下您的三連支持哦~