贪心算法的核心在于利用局部最优解推导全局最优解,但这往往依赖于对问题性质的深刻理解。通过几个经典题目,可以更直观地体会这种策略在不同场景下的应用。
1. LeetCode 376. 摆动序列
求最长摆动序列的关键在于识别极值点。如果在非极值点处截断,后续的选择空间会被压缩。例如在波峰和波谷之间选择一个中间点,会导致无法向另一个方向延伸。因此,策略是尽可能选取波峰或波谷作为序列的端点。
实现时可以通过比较相邻元素的差值符号变化来判断极值点。同时需要注意处理连续相同元素的情况,它们不应计入摆动次数。由于首尾端点在差值判断中可能未被统计,最终结果通常需要加 2。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int left = 0;
int right = 0;
int sz = nums.size();
int ret = 0;
if(sz == 1 || (sz == 2 && (nums[0] == nums[1]))) return 1;
if((nums[0] == nums[sz-1]) && (nums[0] == nums[sz/2])) return 1;
for(int i = 0; i < sz - 1; ++i) {
right = nums[i+1] - nums[i];
if(!right) continue;
if((left * right) < 0) {
ret++;
}
left = right;
}
return ret + 2;
}
};
2. LeetCode 334. 递增的三元子序列
判断是否存在三个递增数字。贪心策略体现在维护两个变量,分别代表当前找到的最小值和次小值。每次遇到新数字时,尝试更新这两个值,使其尽可能小,从而为后续更大的数字留出空间。一旦发现比次小值还大的数,即满足条件。


