贪心算法核心思想与 LeetCode 经典例题解析

贪心算法核心思想与 LeetCode 经典例题解析

贪心算法的核心在于通过局部最优选择达到全局最优。本文通过四道 LeetCode 经典题目深入讲解贪心策略的应用。

1. LeetCode 376. 摆动序列

求一个最长的摆动序列，可以从原数组中删除不符合条件的数。思路是每次选的数字都要在有限的范围内做到尽可能的大或者尽可能的小，以便后续有更多选择。通过比较相邻元素的差值符号变化来确定极值点。

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. 递增的三元子序列

判断原数组里面有没有三个数是呈现递增关系的。思路是维护两个变量 a 和 b，分别代表当前找到的最小值和次小值。每一次判断都在进行筛选，让 a 和 b 变小，方便找到合适的点。